Algorytm genetyczny- problem plecaka

Question

Dzień dobry,

Nowy projekt na studiach to nowy post, mam do napisania algorytm genetyczny który rozwiąże problem plecakowy zakładam że to będzie 0-1 czyli bez dzielenia przedmiotów albo jest i mieści się w plecaku albo nie, poczytałem dość sporo na ten temat teorii i wydaje mi się że wiem mniej więcej jak to ma działać ale problem zaczyna się kiedy trzeba to zakodować. Chromosomy bo z tym jest problem, nie wiem jak zapisać przedmioty w plecaku, myślałem może jako stringa z 0 i 1, myślałem też o tablicy bool'ów ale nic więcej mi do głowy nie przyszło do głowy, więc byłbym wdzięczny za jakiekolwiek wskazówki jak ma kod wyglądać

Comments

Tutaj kolejna, ulepszona wersja. Działa również dla wielu plecaków :)

https://forum.pasja-informatyki.pl/459127/dyskretny-problem-plecakowy-sztuczna-inteligencja-knapsack-algorytm-genetyczny

Jestem pod warażeniem że (wzmocniony) algorytm genetyczny tak dobrze rozwiązuje NP-trudny problem - przynajmniej na przykładowych danych.

Answer 1

Tutaj uruchomienie i kompilacja

https://pastebin.com/b5A3dGNc

[Musialem na pastebin bo tutaj mam ograniczenie do 15kb]

kod

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

typedef double ftyp;
typedef const ftyp cftyp;
typedef std::mt19937_64 Trnd;
typedef std::uniform_int_distribution<int> Tdist;

class MyException : public std::exception {
private:
    const std::string swhat;

public:
    MyException( const char *const swhat ) : swhat(swhat) {
    }

    virtual const char* what() const throw(){
        return swhat.c_str();
    }
};


struct Spec {
    std::vector<bool> genotype;
    ftyp eval;
    ftyp weight;
};

static bool cmpSpec( const Spec &a , const Spec &b ) {
    return a.eval > b.eval;
}

static std::ostream& operator<<( std::ostream& dest, const Spec &spec ) {
    dest << spec.eval << ", " << spec.weight << " [";
    for( size_t i=0 ; i<spec.genotype.size() ; i++ ) {
        std::cout << (spec.genotype[i] ? "1" : "0");
    }
    dest << "]";
    return dest;
}

struct BpItem {
    ftyp weight;
    ftyp value;
};


static std::ostream& operator<<( std::ostream& dest, const BpItem &item ) {
    dest << item.value << " / " << item.weight << " == " << item.value / item.weight;
    return dest;
}

static bool cmpItem( const BpItem &a , const BpItem &b ) {
    return a.value / a.weight > b.value / b.weight;
}


static int getSize() {
    std::cout << "Please input population's size: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n < 1) {
        throw MyException("invalid populations size");
    }
    return n;
}

static int getBests( const int size) {
    std::cout << "Please input number of parents: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n >= size || n < 1) {
        throw MyException("invalid number of parents");
    }
    return n;
}


static ftyp getBackpak() {
    std::cout << "Please input capacity of backpack: ";
    ftyp n;
    std::cin >> n;
    if( std::cin.fail() || n < 0 ) {
        throw MyException("invalid capacity of backpack");
    }
    return n;
}


static ftyp getMutation() {
    std::cout << "Please input frequency of mutations: ";
    ftyp n;
    std::cin >> n;
    if( std::cin.fail() || n < 0 ) {
        throw MyException("infalid mutation");
    }
    return n;
}



static void evalSpec(Spec &spec, cftyp backpack , const std::vector<BpItem> &items ) {
    spec.eval = 0;
    spec.weight = 0;
    for( size_t i=0 ; i<spec.genotype.size() ; i++ ) {
        if( ! spec.genotype[i] ) {
            continue;
        }
        if( spec.weight + items[i].weight > backpack ) {
            continue;
        }
        spec.weight += items[i].weight;
        spec.eval += items[i].value;
    }

}

static void randSpec(
    Spec      &spec ,
    Trnd      &rnd,
    Tdist     &dist,
    const std::vector<BpItem> &items
) {
    spec.genotype.resize( items.size() );
    for( size_t i=0 ; i<items.size() ; i++ ) {
        spec.genotype[i] = dist(rnd) == 1;
    }
}

static void mutationSpec(
    Spec      &spec,
    Trnd      &rnd
) {
    const size_t gen = rnd() % spec.genotype.size();
    spec.genotype[ gen ] = !spec.genotype[ gen ];
}


static void cross(
    const Spec &a,
    const Spec &b,
    Spec       &out,
    Trnd       &rnd,
    Tdist      &dist
) {
    for( size_t i=0 ; i<a.genotype.size() ; i++ ) {
        if( dist(rnd) ) {
            out.genotype[i] = a.genotype[i];
        } else {
            out.genotype[i] = b.genotype[i];
        }
    }
}

int main(int argc, char *argv[]) {
    (void)argc;
    (void)argv;
    try {
        const int seed = (int)time(NULL);
        std::cout << "seed = " << seed << std::endl;
        Trnd rnd( seed );
        Tdist bDist(0,1);                       //binary distribution
        const int size     = getSize();
        const int bests    = getBests( size );  //number of parents (parents are bests)
        Tdist pDist(0,bests-1);                 //parnets distribution
        cftyp     backpack = getBackpak();
        const int mutation = getMutation();
        std::vector<BpItem> items;
        std::cout << "Insert elements (weight,value) [ctrl+d to end]" << std::endl;
        while( true  ) {
            BpItem bpItem;
//            std::cout << "weight: ";
            std::cin >> bpItem.weight;
            if( std::cin.eof() ) {
                break;
            }
            if( std::cin.fail() || bpItem.weight < 0 ) {
                throw MyException("invalid weight");
            }
//            std::cout << "value: ";
            std::cin >> bpItem.value;
            if( std::cin.eof() ) {
                break;
            }
            if( std::cin.fail() || bpItem.value < 0 ) {
                throw MyException("invalid value");
            }
            items.push_back( bpItem );
        }
        std::cout << "Readed " << items.size() << " elements" << std::endl;
        const int start = (int)time(NULL);
        int   lastTime = start;
        std::sort(items.begin(),items.end(),cmpItem);
        for( size_t i=0 ; i<items.size() ; i++ ) {
            std::cout << i << " " << items[i] << std::endl;
        }
        std::vector<Spec>   specs(size);
        for( int i=0 ; i<size ; i++ ) {
            randSpec( specs[i] , rnd, bDist , items );
            evalSpec( specs[i] , backpack, items);
        }
        std::sort(specs.begin(), specs.end(), cmpSpec);
        std::cout << (time(NULL)-start) << "s; best[0]: " << specs[0] << std::endl;
        ftyp bestEval = specs[0].eval;
        for( long long loop=1 ; true ; loop++ ) {
            for( size_t i=bests ; i<specs.size() ; i++ ) {
                cross( specs[ pDist(rnd) ] , specs[ pDist(rnd) ] , specs[ i ] , rnd , bDist  );
                evalSpec( specs[i] , backpack , items );
            }
            for( size_t i=1 ; i<specs.size() ; i++ ) {
                if( rnd() % mutation == 0 ) {
                    mutationSpec( specs[i] , rnd );
                    evalSpec( specs[i] , backpack , items );
                }
            }
            std::sort(specs.begin(), specs.end(), cmpSpec);
            if( bestEval < specs[0].eval || time(NULL) - lastTime > 180 ) {
                bestEval = specs[0].eval;
                std::cout << (time(NULL)-start) << "s; best[" << loop << "]: " << specs[0] << std::endl;
                lastTime = time(NULL);
            }
        }
    }
    catch( std::exception &e ) {
        std::cout << "We have a problem: " << e.what() << std::endl;
    }
    return 0;
}

 

Answer 2

Wprowadziłem jeszcze kilka udoskonaleń do algorytmu genetycznego, głównie rozszerzyłem o wiele plecaków. Spreparowałem też spacjalnie dane, wygląda na to, że algorytm genetyczny znalazł optymalne rozwiązanie dla 5 plecaków i 178 elementów:

Kod źródłowy

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <unordered_set>

typedef double ftyp;
typedef const ftyp cftyp;
typedef std::mt19937_64 Trnd;
typedef std::uniform_int_distribution<int> Tdist;


class MyException : public std::exception {
private:
    const std::string swhat;

public:
    MyException( const char *const swhat ) : swhat(swhat) {
    }

    virtual const char* what() const throw(){
        return swhat.c_str();
    }
};


static std::vector<size_t> specHashes;

struct Spec {
    std::vector<int> genotype;
    ftyp eval;
    ftyp weight;
    bool operator == (const Spec &other) const {
        return genotype == other.genotype;
    }
    std::size_t operator()() const {
        size_t key = 0;
        for( int i=0 ; i<(int)genotype.size() ; i++ ) {
            key ^= specHashes[ (i * 31 + genotype[i]) & 16383 ] + genotype[i];
        }
        return key;
    }
};

namespace std {
  template <>
  struct hash<Spec>
  {
    std::size_t operator()(const Spec& s) const
    {
      return s();
    }
  };
}

static bool cmpSpec( const Spec &a , const Spec &b ) {
    return a.eval > b.eval;
}

static std::ostream& operator<<( std::ostream& dest, const Spec &spec ) {
    dest << spec.eval << ", " << spec.weight << " [";
    for( size_t i=0 ; i<spec.genotype.size() ; i++ ) {
        std::cout << spec.genotype[i];
        if( i < spec.genotype.size() - 1 ) {
            std::cout << ",";
        }
    }
    dest << "]";
    return dest;
}

//MM: The stats of whole  population
struct StPops {
    ftyp avg;     // average eval
    ftyp repeats; // number of the repeats
};

static std::ostream& operator<<( std::ostream& dest, const StPops &stat ) {
    dest << "repeats:" << stat.repeats << " avgeval:" << stat.avg;
    return dest;
}

struct BpItem {
    ftyp weight;
    ftyp value;
};

static std::ostream& operator<<( std::ostream& dest, const BpItem &item ) {
    dest << item.value << " / " << item.weight << " == " << item.value / item.weight;
    return dest;
}


static bool cmpItem( const BpItem &a , const BpItem &b ) {
    return a.value / a.weight > b.value / b.weight;
}

static int getSeed() {
    std::cout << "Please input random seed (zero to random): ";
    int n;
    std::cin >> n;
    if( std::cin.fail() ) {
        throw MyException("invalid random seed");
    }
    if( n < 1 ) {
        n = (int)time(NULL);
    }
    return n;
}

static int getLoops() {
    std::cout << "Please input max loops (zero to inifinite): ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n < 0 ) {
        throw MyException("invalid max loops");
    }
    return n;
}

static int getSize() {
    std::cout << "Please input population's size: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n < 1) {
        throw MyException("invalid populations size");
    }
    return n;
}

static int getBests( const int size) {
    std::cout << "Please input number of parents: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n >= size || n < 1) {
        throw MyException("invalid number of parents");
    }
    return n;
}


static std::vector<ftyp> getBackpacks() {
    std::vector<ftyp> backpacks;
    std::cout << "Please input number of backpacks: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n < 1 ) {
        throw MyException("invalid number of backpacks");
    }
    for( int i=0 ; i<n ; i++ ) {
        std::cout << (i+1) << " please input capacity of backpack: ";
        ftyp c;
        std::cin >> c;
        if( std::cin.fail() || c <= 0 ) {
            throw MyException("invalid capacity of backpack");
        }
        backpacks.push_back( c );
    }
    return backpacks;
}

static int getMutation() {
    std::cout << "Please input frequency of mutations: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n < 0 ) {
        throw MyException("infalid mutation");
    }
    return n;
}

static std::vector<BpItem> getItems() {
    std::vector<BpItem> items;
    std::cout << "Please insert number of items:";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n < 1 ) {
        throw MyException("invalid number of items");
    }
    items.resize( n );

    for( int i=0 ; i<n ; i++ ) {
        BpItem bpItem;
        std::cout << "insert " << (i+1) << " weight: ";
        std::cin >> bpItem.weight;
        if( std::cin.fail() || bpItem.weight <= 0 ) {
            throw MyException("invalid weight");
        }
        std::cout << "insert " << (i+1) << " value: ";
        std::cin >> bpItem.value;
        if( std::cin.fail() || bpItem.value <= 0 ) {
            throw MyException("invalid value");
        }
        items[i] =  bpItem ;
    }
    std::sort(items.begin(),items.end(),cmpItem);
    for( size_t i=0 ; i<items.size() ; i++ ) {
        std::cout << (i+1) << " " << items[i] << std::endl;
    }
    std::cout << "Readed " << items.size() << " elements" << std::endl;
    return items;
}

static void evalSpec(Spec &spec, const std::vector<ftyp> backpacks , const std::vector<BpItem> &items ) {
    spec.eval   = 0;
    spec.weight = 0;
    std::vector<ftyp> weights( backpacks.size() , 0 );
    for( size_t i=0 ; i<spec.genotype.size() ; i++ ) {
        if( spec.genotype[i] == 0 ) {
            continue;
        }
        const int nr = spec.genotype[i] - 1;
        if( weights[nr] + items[i].weight > backpacks[nr] ) {
            spec.eval -= 0.001; // penal value
            continue;
        }
        weights[nr] += items[i].weight;
        spec.weight += items[i].weight;
        spec.eval += items[i].value;
    }
}

static void randSpec(
    Spec      &spec ,
    Trnd      &rnd ,
    const std::vector<BpItem> &items,
    const std::vector<ftyp> backpacks
) {
    spec.genotype.resize( items.size() );
    for( size_t i=0 ; i<items.size() ; i++ ) {
        spec.genotype[i] = ( rnd() % ( backpacks.size() + 1 ) );
    }
}

static void mutationSpec(
    Spec      &spec,
    Trnd      &rnd ,
    const std::vector<ftyp> backpacks
) {
    const size_t gen = rnd() % spec.genotype.size();
    spec.genotype[ gen ] = rnd() % (backpacks.size() + 1);
}


static void cross2(
    const Spec &a,
    const Spec &b,
    Spec       &out,
    Trnd       &rnd
) {
    for( size_t i=0 ; i<a.genotype.size() ; i++ ) {
        if( rnd() & 1 ) {
            out.genotype[i] = a.genotype[i];
        } else {
            out.genotype[i] = b.genotype[i];
        }
    }
}

static void cross1(
    const Spec &a,
    const Spec &b,
    Spec       &out,
    Trnd       &rnd
) {
    size_t x = rnd() % (a.genotype.size()-1) + 1;
    for( size_t i=0 ; i<x ; i++ ) {
        out.genotype[i] = a.genotype[i];
    }
    for( size_t i=x ; i<a.genotype.size() ; i++ ) {
        out.genotype[i] = b.genotype[i];
    }
}


static StPops mkStats( const std::vector<Spec> &specs ) {
    StPops stats;
    stats.avg     = 0;
    stats.repeats = 0;
    std::unordered_set<Spec> rep ( specs.size() );
    for( int i=0 ; i<(int)specs.size() ; i++ ) {
        if( rep.find( specs[i] ) == rep.end() ) {
            rep.insert( specs[i] );
        } else {
            stats.repeats ++ ;
        }
        stats.avg += specs[i].eval;
    }
    stats.avg /= specs.size();
    return stats;
}


int main(int argc, char *argv[]) {
    (void)argc;
    (void)argv;
    try {
        const int seed     = getSeed();
        std::cout << "seed = " << seed << std::endl;
        const int loops    = getLoops();
        const int size     = getSize();
        const int bests    = getBests( size );  //number of parents (parents are bests)
        const int mutation = getMutation();
        const std::vector<ftyp> backpacks = getBackpacks();
        const std::vector<BpItem> items = getItems();

        Trnd rnd( seed );
        Tdist pDist(0,bests-1);                 //parnets distribution

        for( int i=0 ; i<16384 ; i++ ) {
            specHashes.push_back( rnd() );
        }

        const time_t start = (int)time(NULL);
        time_t lastTime    = start;

        std::vector<Spec> specs(size);
        for( int i=0 ; i<size ; i++ ) {
            randSpec( specs[i] , rnd       , items , backpacks );
            evalSpec( specs[i] , backpacks , items );
        }

        std::sort(specs.begin(), specs.end(), cmpSpec);
        std::cout << (time(NULL)-start) << "s; best[0]: " << specs[0] << std::endl;
        std::cout << mkStats( specs ) << std::endl;

        ftyp bestEval = specs[0].eval;
        for( int loop=1 ; loops == 0 || loop <= loops ; loop++ ) {

            for( size_t i=bests ; i<specs.size() ; i++ ) {
                cross1( specs[ pDist(rnd) ] , specs[ pDist(rnd) ] , specs[ i ] , rnd );
                evalSpec( specs[i] , backpacks , items );
            }

            for( size_t i=1 ; i<specs.size() ; i++ ) {
                if( rnd() % mutation == 0 ) {
                    mutationSpec( specs[i] , rnd , backpacks );
                    evalSpec( specs[i] , backpacks , items );
                }
            }

            std::sort(specs.begin(), specs.end(), cmpSpec);

            if( bestEval < specs[0].eval || time(NULL) - lastTime > 10 || loop == loops ) {
                bestEval = specs[0].eval;
                std::cout << (time(NULL)-start) << "s; best[" << loop << "]: " << specs[0] << std::endl;
                std::cout << mkStats( specs ) << std::endl;
                lastTime = time(NULL);
            }
        }
    }
    catch( std::exception &e ) {
        std::cout << "We have a problem: " << e.what() << std::endl;
    }
    return 0;
}

 

Dane, można wkleić w konsoli:

1234
100
100000
10000
20

5

210
220
250
330
350

178

1
6
15
19
3
6
1
3
12
16
9
14
14
15
6
11
13
15
13
15
8
10
6
11
9
11
5
8
1
2
9
12
9
12
15
18
8
12
5
7
5
9
5
9
3
7
11
14
7
9
14
19
3
8
7
8
10
15
8
13
13
15
12
14
3
5
11
14
5
10
12
15
6
11
5
7
5
7
2
5
5
9
8
11
3
8
5
10
4
8
2
6
1
2
10
13
9
12
1
4
1
6
8
10
12
16
13
16
7
9
15
18
11
15
6
7
15
16
18
23
8
12
9
13
6
9
4
8
11
13
3
4
10
14
10
15
13
14
1
6
14
17
14
15
14
19
10
12
10
11
7
8
15
20
2
3
4
9
6
8
2
3
2
6
1
4
2
6
1
4
17
19
6
11
15
20
14
18
15
17
8
13
2
7
23
26
6
11
4
7
21
24
19
23
16
20
21
24
15
20
1
5
8
11
11
14
10
11
9
13
10
15
4
8
13
15
15
16
10
14
1
6
13
17
21
23
1
4
8
12
17
20
13
17
1
2
21
22
8
12
5
9
10
12
11
15
1
2
2
7
19
21
6
7
18
19
12
13
4
8
4
6
15
19
12
15
22
25
21
22
19
22
23
28
12
14
11
16
19
22
17
18
20
23
1
4
22
23
15
16




16
8
10
5
12
6
24
12
14
7
12
6
24
12
20
10
18
9
6
3
14
7
24
12
16
8
18
9
6
3
22
11
18
9
20
10
10
5
6
3
22
11
20
10
16
8
20
10
20
10
20
10
24
12
12
6
18
9
10
5
8
4
22
11
24
12

 

Kompilacja, uruchomienie:

g++ -Wall -Wextra -pedantic -O3 -std=c++11 main.cpp -o genetic
time ./genetic

 

Answer 3

Mniej/więcej tak, nie sprawdzałem czy liczy poprawnie.

g++ -std=c++11 -O3 main.cpp -o genetic
./genetic 
seed = 1573689670
Podaj rozmiar populacji: 10000
Podaj ilosc rodzicow: 8000
Podaj udzwig plecaka: 500
Podaj raz na ile razy mayc mutacja: 10000
Podaj elementy (waga,wartość) [ctrl+d kończy]
30.45
51.06
57.44
36.24
81.23
22.67
20.24
28
36.34
61.8
18.18
80.16
63.19
13.57
72.09
62.74
69.62
80.16
53.71
49.88
23.76
17.23
57.85
63.9
44.62
66.81
44.08
70.13
9.69
12.77
62.87
83.5
75.53
25.67
80.86
28.33
29.36
25.96
66.04
27.96
50.14
21.5
21.89
62.87
30.75
17.11
99.08
97.45
73.1
88.17
17.88
61.52
48.45
77.89
80.76
84.56
25.27
92.95
4.22
17.4
90.29
68.03
57.05
54.94
99.22
39.96
64.89
25.48
84.96
92.7
7.71
81.44
57.92
79.34
83.06
43.89
91.94
76.71
22.99
37.67
45.24
74.57
73.2
67.29
89.19
38.62
70.28
95.27
88.37
18.12
19.25
68.77
63.08
81.82
49.16
23.97
26.15
68.24
97.79
25.64
69.69
16.68
56.5
52.26
19.1
82.9
36.24
88.26
71.98
60.85
27.32
83.75
26.78
85.1
95.54
4.83
11.64
9.71
42.56
54.65
22.87
83.18
71.51
66.79
57.14
12.86
64.85
42.56
27.56
28.77
84.08
36.23
76.72
17.39
41.64
64.48
17.09
0.84
29.35
24.63
46.65
51.31
3.3
41.05
31.14
27.91
81.59
76.61
87.22
70.82
47.9
8.26
11.26
73.64
26.38
78.15
1.04
12.69
75.23
0.99
91.23
90.74
43.99
42.28
66.16
47.79
74.1
64.79
66.38
88.25
54.25
11.98
73.51
37.92
3.8
64
62.22
31.52
82.03
89.42
73.91
8.81
20.21
86.32
91.74
7.29
43.59
49.67
64.4
95.01
89.58
35.8
56.4
52.06
15.39
84.18
39.21
58.99
17.69
86.82
Wczyano 100 elementow
best[0]: 996.05 [0001010000001100100101000110110000010000101100001010010110111000010011000010011011010011111110011101]
best[7]: 1013.48 [0001010011001110001001010101110100011110111100001010100100111000000110010010101111001001111001000101]
best[8]: 1066.96 [1001110010000110000001101111110100011000011111000110011100101101010111110110000001011101011000001110]
best[13]: 1076.96 [1001110000011001000001000110110101111000011101010110110100110100010110010001010010100110010100111111]
best[17]: 1111.55 [1001110110110110000001000100101000010010010010000111101010010001011001010001011111110011001110110110]
best[20]: 1130.19 [1001010000010110000001001111101000011010111110000000110000000001001000111011000010110101010101000001]
best[29]: 1140.55 [1001110000001111001001000101111001011010001110011000010111001010011100010010111111101111100100110011]
best[30]: 1150.9 [1001110000001111001001001100110000011000000111100011110000011101001100010001110100000001001101110011]
best[32]: 1167.35 [1000110000000011000001000110110000110001101111000100111111000010010000110000111010101010111111001001]
best[33]: 1198.59 [0001010010101100000001001110100000010011011001010101111110010000000101010101001011110101111101101110]
best[41]: 1206.73 [1000110010011010000001000110100101011010010010000100100000010000000100110101101111000001011111010111]
best[42]: 1227.66 [1000110000001100000001000101110000011000100011100110111001000001100000011100101000110001011011010110]
best[50]: 1229.79 [1001110000011101000001000110110010010000011111100001110000000000000101011010100101001111111000000101]
best[51]: 1239.06 [1000110000000000000001000100110000011000100001100001010100110000001100111011111001011101101010011011]
best[54]: 1244.4 [1000110000001110001001000110100000011000000001001100100011000101110000011110100000110011100011001000]
best[59]: 1254.9 [1000110000001101000001000110110000011001011101000001101101011100011101010101100010011101000010111001]
best[64]: 1264.18 [1001110000001100000001000110100000010001000001101010101010011100100001110010000111110111001101110101]
best[76]: 1268.84 [1000110000001111000001001100110000010000000001000100100111001111100101111001101101110111001001011000]
best[78]: 1270.99 [1001110000001110000001000110110100010001000000001010100101000101001100011001100110011101001000000011]
best[82]: 1272.76 [1000110000000110000001000110110000011000100101000011100001010110111100010001001111101111000100001111]
best[84]: 1277.73 [1001110000001110000001000110100000010001100000001100111101000001110001011001110010011111000000000000]
best[87]: 1295.94 [1001110000001111000001000110110000010000000000000000111011010011110001111101111010111111000000111111]
best[101]: 1299.55 [1000110000000110000001000110110000010000000101001000111101010010010101110000101110000001010011011010]
best[103]: 1322.05 [1000110000001111000001000110110000010000000001001000011010010111111001110101111110110101110100101100]
best[113]: 1336.71 [1000110000001111000001000110110000010000000001000000111010010111110000111111111010010101110111100110]
best[115]: 1342.23 [1001110000001111000001000110100000010000000001000000100010001000101101111110101011010101110011100110]
best[134]: 1360.25 [1000110000001111000001000110110000010001000001000000101010000011000000110000100010100001000011001011]
best[137]: 1374.98 [1000110000001101000001000110110000010000000001001100100111010101010100111101110000001111011000101101]
best[138]: 1400.9 [1000110000001011000001000110110000010000000001000000100110010100001100010101111111111111101101000110]
best[221]: 1402.61 [1000110000001101000001000110110000010000000001000000100110001010000100010000111110110011010110101110]
best[269]: 1436.14 [1000110000001100000001000110110000010000000001000000110110001010110001110101111110100011000011101000]
best[327]: 1463.39 [1001110000000111000001000110110000010000000001000000100111001101000000110010101100001011001110001001]
best[344]: 1487.46 [1000110000001110000001000110110000010000000001001000110101001010010100010001111110010011110001001111]
best[363]: 1494.19 [1000110000001100000001000110110000010000000001000000110111001011000000010100101100111111001001000011]
best[364]: 1588.55 [1000110000000101000001000100110000010000000001001000110110000000000000010110101000011001010110000111]
best[375]: 1592.07 [1000110000000110000001000110110000010000000001001000110110001000001000010100101110011011010100001101]
best[401]: 1592.57 [1000110000000110000001000110110000010000000001001000110111001001000000010010101011001101010010010101]
best[404]: 1601.98 [1000110000000110000001000110110000010000000001000000110110001000000000010010111001110001000110011111]
best[419]: 1602.48 [1000110000000110000001000110110000010000000001000000110110001000000000010100111000011111011000000101]
best[432]: 1605.62 [1000110000000110000001000110110000010000000001000000110110000000000000010000111010010011000100101111]
best[438]: 1625.88 [1001110000000100000001000110110000010000000001000000110110001000010000010100101110110011100111100101]
best[443]: 1636.76 [1001110000000010000001000110110000010000000001001000110110001000010000010000101010011011000101110101]
best[453]: 1646.67 [1001110000000010000001000110110000010000000001000000110110001000000000010000111010100011001110101101]
best[510]: 1679.15 [1000110000000110000001000100110000010000000001001000110110001000000000010000111100000001000101101101]
best[519]: 1686.91 [1000110000000010000001000110110000010000000001001000110110001000000000010000111010110001111110100111]

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

typedef double ftyp;
typedef const ftyp cftyp;
typedef std::ranlux48 Trnd;
typedef std::uniform_int_distribution<int> Tdist;

class MyException : public std::exception {
private:
    const std::string swhat;

public:
    MyException( const char *const swhat ) : swhat(swhat) {
    }

    virtual const char* what() const throw(){
        return swhat.c_str();
    }
};


struct Spec {
    std::vector<bool> genotype;
    ftyp eval;
};

static bool cmpSpec( const Spec &a , const Spec &b ) {
    return a.eval > b.eval;
}

static std::ostream& operator<<( std::ostream& dest, const Spec &spec ) {
    std::cout << spec.eval << " [";
    for( size_t i=0 ; i<spec.genotype.size() ; i++ ) {
        std::cout << (spec.genotype[i] ? "1" : "0");
    }
    std::cout << "]";
    return dest;
}

struct BpItem {
    ftyp weight;
    ftyp value;
};

static int getSize() {
    std::cout << "Podaj rozmiar populacji: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n < 1) {
        throw MyException("Nieprawidlowy rozmiar populacji");
    }
    return n;
}

static int getBests( const int size) {
    std::cout << "Podaj ilosc rodzicow: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n >= size || n < 1) {
        throw MyException("Nieprawidlowa ilosc rodzicow");
    }
    return n;
}


static ftyp getBackpak() {
    std::cout << "Podaj udzwig plecaka: ";
    ftyp n;
    std::cin >> n;
    if( std::cin.fail() || n < 0 ) {
        throw MyException("Nieprawidlowy udzwig plecaka");
    }
    return n;
}


static ftyp getMutation() {
    std::cout << "Podaj raz na ile razy mayc mutacja: ";
    ftyp n;
    std::cin >> n;
    if( std::cin.fail() || n < 0 ) {
        throw MyException("Nieprawidlowa mutacja");
    }
    return n;
}



static void evalSpec(Spec &spec, cftyp backpack , const std::vector<BpItem> &items ) {
    ftyp sumOfWeight = 0;
    spec.eval = 0;
    for( size_t i=0 ; i<spec.genotype.size() ; i++ ) {
        if( ! spec.genotype[i] ) {
            continue;
        }
        if( sumOfWeight + items[i].weight > backpack ) {
            continue;
        }
        sumOfWeight += items[i].weight;
        spec.eval += items[i].value;
    }
}

static void randSpec(
    Spec      &spec ,
    Trnd      &rnd,
    Tdist     &dist,
    const std::vector<BpItem> &items
) {
    for( size_t i=0 ; i<items.size() ; i++ ) {
        spec.genotype.push_back( dist(rnd) == 1 );
    }
}

static void mutationSpec(
    Spec      &spec,
    Trnd      &rnd
) {
    const size_t gen = rnd() % spec.genotype.size();
    spec.genotype[ gen ] = !spec.genotype[ gen ];
}


static void cross(
    const Spec &a,
    const Spec &b,
    Spec       &out,
    Trnd       &rnd,
    Tdist      &dist
) {
    for( size_t i=0 ; i<a.genotype.size() ; i++ ) {
        if( dist(rnd) ) {
            out.genotype[i] = a.genotype[i];
        } else {
            out.genotype[i] = b.genotype[i];
        }
    }
}

int main(int argc, char *argv[]) {
    (void)argc;
    (void)argv;
    try {
        const int seed = (int)time(NULL);
        std::cout << "seed = " << seed << std::endl;
        Trnd rnd( seed );
        Tdist bDist(0,1);                       //binary distribution
        const int size     = getSize();
        const int bests    = getBests( size );  //number of parents (parents are bests)
        Tdist pDist(0,bests-1);                 //parnets distribution
        cftyp     backpack = getBackpak();
        const int mutation = getMutation();
        std::vector<BpItem> items;
        std::cout << "Podaj elementy (waga,wartość) [ctrl+d kończy]" << std::endl;
        while( true  ) {
            BpItem bpItem;
//            std::cout << "weight: ";
            std::cin >> bpItem.weight;
            if( std::cin.eof() ) {
                break;
            }
            if( std::cin.fail() || bpItem.weight < 0 ) {
                throw MyException("Nieprawidlowa waga");
            }
//            std::cout << "value: ";
            std::cin >> bpItem.value;
            if( std::cin.eof() ) {
                break;
            }
            if( std::cin.fail() || bpItem.value < 0 ) {
                throw MyException("Nieprawidlowa wartosc");
            }
            items.push_back( bpItem );
        }
        std::cout << "Wczyano " << items.size() << " elementow" << std::endl;
        std::vector<Spec>   specs(size);
        for( int i=0 ; i<size ; i++ ) {
            randSpec( specs[i] , rnd, bDist , items );
            evalSpec( specs[i] , backpack, items);
        }
        std::sort(specs.begin(), specs.end(), cmpSpec);
        std::cout << "best[0]: " << specs[0] << std::endl;
        ftyp bestEval = specs[0].eval;
        for( long long loop=1 ; true ; loop++ ) {
            for( size_t i=bests ; i<specs.size() ; i++ ) {
                cross( specs[ pDist(rnd) ] , specs[ pDist(rnd) ] , specs[ i ] , rnd , bDist  );
                evalSpec( specs[i] , backpack , items );
            }
            for( size_t i=1 ; i<specs.size() ; i++ ) {
                if( rnd() % mutation == 0 ) {
                    mutationSpec( specs[i] , rnd );
                    evalSpec( specs[i] , backpack , items );
                }
            }
            std::sort(specs.begin(), specs.end(), cmpSpec);
            if( bestEval < specs[0].eval ) {
                bestEval = specs[0].eval;
                std::cout << "best[" << loop << "]: " << specs[0] << std::endl;
            }
        }
    }
    catch( std::exception &e ) {
        std::cout << "Wystapił błąd: " << e.what() << std::endl;
    }
    return 0;
}

 

Answer 4

Tu minimalnie ulepszona wersja:

g++ -std=c++11 -O3 main.cpp -o genetic
root@SSDB:/home/m/Dokumenty/c/eduGetLineZero# time ./genetic                        
seed = 1573694515
Podaj rozmiar populacji: 100000
Podaj ilosc rodzicow: 50000
Podaj udzwig plecaka: 2000
Podaj raz na ile razy mayc mutacja: 10000
Podaj elementy (waga,wartość) [ctrl+d kończy]
60.9
54.4
41.76
3.58
7.94
84.25
91.7
91.4
38.85
0.4
3.3
44.46
77.09
29.61
47.22
12.12
18.29
61.71
15.59
63.67
42.84
92.92
3.2
43.81
74.44
19.67
41.4
62.09
23.98
33.96
53.34
2.97
39.53
80.08
5.63
15.37
82.18
36.22
59.57
5.5
0.18
10.68
65
81.51
32.85
73.79
24.06
73.95
22.41
31.68
5.75
89.74
59.1
29.8
56.13
5.79
76.07
39.92
32.46
78.4
76.42
11
97.11
21.37
54.33
75.41
60.64
47.62
25.41
81.42
14.78
88.96
56.37
81.9
35.82
16.04
42.35
42.34
25.76
88.48
63.27
44.81
71.77
7.1
49.56
26.26
31.66
36.36
43.84
12.53
47.11
68.74
72.03
85.93
34.7
64.92
5.41
74.03
8.91
0.89
71.15
51.43
14.01
34.94
22.98
27.1
32.04
80.62
77.59
56.45
8.03
35.25
71.63
76.49
11.01
72.88
51.73
91.01
31.81
69.8
60.08
94.75
78.24
25.55
82.13
74.49
3.25
34.26
63.25
86.11
49.75
60.4
69.89
50.5
13.68
15.27
44.46
13.92
71.94
7.73
79.45
74.9
87.07
98.1
58.66
85.22
79.18
6.18
57.06
72.96
86.13
18.04
31.8
99.71
75.22
54.04
29.45
46.16
12.97
18.59
85.77
11.72
94.42
47.67
25.86
37.58
63.79
73.79
69.33
56.02
75.05
62.51
3.83
50.59
62.59
60.91
1.8
90.83
56.44
67.85
37.61
69.83
29.99
53.49
38.73
72.91
2.26
97.25
61.66
10.23
54.49
67.64
79.98
84.34
31.55
49.29
14.61
98.07
31.48
62.85
98.04
96.28
36.33
50.87
33.2
53.48
37.25
30.89
15.77
32.62
87.92
14.59
31.63
99.69
95.22
40.94
60.15
71.15
16.97
78.5
34.89
16.87
96.6
19.88
13.21
77.02
46.41
85.2
12.17
90.9
42.47
76.12
79.29
22.93
99.8
74.72
32.14
20.76
56.95
43.87
53.93
28.49
8.38
63.98
53.23
61.35
76.22
53.47
83.55
38.18
98.16
56.91
37.82
74.35
4.08
5.08
78.97
3.59
77.45
84.84
20.67
72.27
74.01
41.63
90.66
88.72
33.58
81.62
15.44
48.44
20.82
25.51
18.55
93.33
60.87
87.75
62.13
66.82
54.73
54
60.73
98.24
59.63
42.04
95.26
50.86
42.98
94.9
88.63
75.04
26
24.08
42.3
89.12
12.23
83.99
2.8
90.22
97.07
96.08

Wczyano 150 elementow
best[0]: 3381.19, 1999.7 [101011001001011010000001010000000111110100000011111011010110000001001000110011010110101110110100001011010000110101100110000001011100011101010001010100]
31s; best[2]: 3453.94, 1999.85 [101001101011010011011111010111001011000010000101011100010110001110010001100000110000101111011101111001000010100100111100110101111110000100110111111011]
33s; best[3]: 3582.6, 1999.66 [111001011111001010001111101000001111111100000011100110010101100011010011000011110111001000101101011000100110011100101111001001100100111001011010001110]
35s; best[4]: 3641.05, 1994.5 [011011001001000001001111111001000011101100100011010111011101100000010001100011110000001110011001011110001010010001110101000011111010110010101110001101]
37s; best[5]: 3743.07, 1995.58 [011001101111110011000001011001001011100100100010110110010101101110001000001010100011101110100111011010001010111111100000001001110010000101110010111110]
39s; best[6]: 3877.6, 1996.61 [011001001100001010000111011001000011100110000000110001111110100010100000100010010001011010001101011111101110000010110000000100110111001100111010001110]
44s; best[8]: 3930.57, 1995.82 [000001001101001000000001111001001011110100010010101101010101100010000001101010100000011011110101111111110010100011100101010110101100110100010010000110]
46s; best[9]: 4034.31, 1998.93 [001001011101010011000111110101001011110110001010100100010111100100000000001010100010001011001101011000100010111111110110110101101000100011000101110110]
50s; best[11]: 4185.72, 1999.07 [101001010101011000001011010001001011110100000111100101010111100111110010100010110000001011011100001101100010010011100010111100111010110110000000101010]
52s; best[12]: 4186.25, 1992.5 [101001001110010011000101110001000111100100000101100101010111101110010010100010110000100010101100001110101010011001100011010100101010101010110010010110]
55s; best[13]: 4295.49, 1981.17 [001101001101000010001111110001000011000100010100100111010111100110010001100010000000000010011100011011001010110011111000000100010010011011000010011111]
57s; best[14]: 4306.62, 1980.44 [001001001111000010001111010001000011101110000011100111011111000011000000100010100001001110110101101101001010110010110011111010000011001011011101110010]
61s; best[16]: 4423.07, 1994.3 [001001000111000011001111110001001111110100100001100111011111000101000000001010100001001011101100001101011010111010100010010000100010001111111000101110]
64s; best[17]: 4430.05, 1981.32 [001001001111011011001011110001001011000100010110100101011111100100110001100011000000001011101100101000110010010011110100010000000000010011001110101111]
66s; best[18]: 4580.48, 1992.36 [001001001111001010001011110001001011100100010111100101011111101110010000000011000010001010101100011101101010010011100010011100100110011110100011110111]
74s; best[21]: 4682.99, 1992.25 [001001001101010011001011010000001011101100000101100001011111100110010000101010110010001011111101011101101010010011110000011000100010111111110101001111]
80s; best[24]: 4683.64, 1975.94 [001101001111010011001011010001000011100100010101110101011111100101000000100010000000001010111101011101101010110011110001011000100010011011111011100111]
83s; best[25]: 4752.79, 1997.07 [001001001111010011000111010001001011000100000111100101010111100101010000101010100010001010111101011001000010010011110000011000110110010011011000001111]
85s; best[26]: 4779.02, 1996.49 [001001001111001011001011110001001011100100010111100101011111100110000000101010110000001010111101001100111010010011110000011000010110011011000001001111]
89s; best[28]: 4806.84, 1996.32 [001001001111010011000011110001001011000100000101100101010111100110010000101010110001001011111101011100111010010011110000010000100100011110001001011110]
94s; best[30]: 4845.39, 1989.39 [001001001111011011001011110001001011000100010101100111010111100110010000101010010010001011111101111101001010010011110000010000100010011111001001101111]
98s; best[32]: 4846.74, 1998.12 [001001001111011011001111110001000011100100000101110101010111100101000000101010110010001010101101011100101010110011110000011000100010011011101001111110]
100s; best[33]: 4871.76, 1992.47 [001001001111010011001011110001001011100100000101100101011111100111000000100010100011001010111100011101101010110011110000010000110010001011001001001111]
102s; best[34]: 4889.05, 1990.76 [001001001111010011001011110001001011100100000001100101010111100111000000001010110010001011111100011101101010010011110000010000110110011011101001101110]
104s; best[35]: 4920.32, 1990.7 [001001001111011011001011110001001011100100000001100111010111100110010000101010110010001011111100011101101010010011110000011000100010011111001001101110]
113s; best[39]: 4926.67, 1990.77 [001001001111010011001111110001001011100100000101100101010111100111010000101010100000001010111101011101101010010011110000010000100010011011001001101111]
115s; best[40]: 4929.2, 1998.61 [001001001111011011001111010001001011100100000101100111010111100110000000100010110010001010111100011101101010010011110000011000110010011011101001101110]
117s; best[41]: 4937.08, 1997.92 [001001001111011011001111110001000011100100000101100101010111100110000000101010110010001011111100011101101010110011110000010000100010011011001001001111]
119s; best[42]: 4947.33, 1999.83 [001001001111011011001011110001001011100100000101100111010111100111000000101010110010001011111100011101101010010011110000010000100010011011001001001111]
124s; best[44]: 4948.05, 1998 [001001001111011011001111110001001011100100000101100101010111100110000000101010100010001010111101011101101010010011110000010000100010011111001001101111]
131s; best[47]: 4949.16, 1999.09 [001001001111011011001111110001001011100100000101100101010111100111010000101010110010001010111100011101101010010011110000010000100010011011001001101111]
135s; best[49]: 4949.72, 1999.89 [001001001111011011001111110001001011100100000101100101010111100110000000101010110010001010111100011101101010110011110000010000110010011011001001101111]
143s; best[53]: 4950.61, 1999.8 [001001001111011011001011110001001011100100000101100101010111100111000000101010110010001010111101011101101010010011110000010000110010011111001001101111]

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

typedef double ftyp;
typedef const ftyp cftyp;
typedef std::ranlux48 Trnd;
typedef std::uniform_int_distribution<int> Tdist;

class MyException : public std::exception {
private:
    const std::string swhat;

public:
    MyException( const char *const swhat ) : swhat(swhat) {
    }

    virtual const char* what() const throw(){
        return swhat.c_str();
    }
};


struct Spec {
    std::vector<bool> genotype;
    ftyp eval;
    ftyp weight;
};

static bool cmpSpec( const Spec &a , const Spec &b ) {
    return a.eval > b.eval;
}

static std::ostream& operator<<( std::ostream& dest, const Spec &spec ) {
    std::cout << spec.eval << ", " << spec.weight << " [";
    for( size_t i=0 ; i<spec.genotype.size() ; i++ ) {
        std::cout << (spec.genotype[i] ? "1" : "0");
    }
    std::cout << "]";
    return dest;
}

struct BpItem {
    ftyp weight;
    ftyp value;
};

static int getSize() {
    std::cout << "Podaj rozmiar populacji: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n < 1) {
        throw MyException("Nieprawidlowy rozmiar populacji");
    }
    return n;
}

static int getBests( const int size) {
    std::cout << "Podaj ilosc rodzicow: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n >= size || n < 1) {
        throw MyException("Nieprawidlowa ilosc rodzicow");
    }
    return n;
}


static ftyp getBackpak() {
    std::cout << "Podaj udzwig plecaka: ";
    ftyp n;
    std::cin >> n;
    if( std::cin.fail() || n < 0 ) {
        throw MyException("Nieprawidlowy udzwig plecaka");
    }
    return n;
}


static ftyp getMutation() {
    std::cout << "Podaj raz na ile razy mayc mutacja: ";
    ftyp n;
    std::cin >> n;
    if( std::cin.fail() || n < 0 ) {
        throw MyException("Nieprawidlowa mutacja");
    }
    return n;
}



static void evalSpec(Spec &spec, cftyp backpack , const std::vector<BpItem> &items ) {
    spec.eval = 0;
    spec.weight = 0;
    for( size_t i=0 ; i<spec.genotype.size() ; i++ ) {
        if( ! spec.genotype[i] ) {
            continue;
        }
        if( spec.weight + items[i].weight > backpack ) {
            continue;
        }
        spec.weight += items[i].weight;
        spec.eval += items[i].value;
    }

}

static void randSpec(
    Spec      &spec ,
    Trnd      &rnd,
    Tdist     &dist,
    const std::vector<BpItem> &items
) {
    for( size_t i=0 ; i<items.size() ; i++ ) {
        spec.genotype.push_back( dist(rnd) == 1 );
    }
}

static void mutationSpec(
    Spec      &spec,
    Trnd      &rnd
) {
    const size_t gen = rnd() % spec.genotype.size();
    spec.genotype[ gen ] = !spec.genotype[ gen ];
}


static void cross(
    const Spec &a,
    const Spec &b,
    Spec       &out,
    Trnd       &rnd,
    Tdist      &dist
) {
    for( size_t i=0 ; i<a.genotype.size() ; i++ ) {
        if( dist(rnd) ) {
            out.genotype[i] = a.genotype[i];
        } else {
            out.genotype[i] = b.genotype[i];
        }
    }
}

int main(int argc, char *argv[]) {
    (void)argc;
    (void)argv;
    try {
        const int start = (int)time(NULL);
        int   lastTime = start;
        const int seed = start;
        std::cout << "seed = " << seed << std::endl;
        Trnd rnd( seed );
        Tdist bDist(0,1);                       //binary distribution
        const int size     = getSize();
        const int bests    = getBests( size );  //number of parents (parents are bests)
        Tdist pDist(0,bests-1);                 //parnets distribution
        cftyp     backpack = getBackpak();
        const int mutation = getMutation();
        std::vector<BpItem> items;
        std::cout << "Podaj elementy (waga,wartość) [ctrl+d kończy]" << std::endl;
        while( true  ) {
            BpItem bpItem;
//            std::cout << "weight: ";
            std::cin >> bpItem.weight;
            if( std::cin.eof() ) {
                break;
            }
            if( std::cin.fail() || bpItem.weight < 0 ) {
                throw MyException("Nieprawidlowa waga");
            }
//            std::cout << "value: ";
            std::cin >> bpItem.value;
            if( std::cin.eof() ) {
                break;
            }
            if( std::cin.fail() || bpItem.value < 0 ) {
                throw MyException("Nieprawidlowa wartosc");
            }
            items.push_back( bpItem );
        }
        std::cout << "Wczyano " << items.size() << " elementow" << std::endl;
        std::vector<Spec>   specs(size);
        for( int i=0 ; i<size ; i++ ) {
            randSpec( specs[i] , rnd, bDist , items );
            evalSpec( specs[i] , backpack, items);
        }
        std::sort(specs.begin(), specs.end(), cmpSpec);
        std::cout << "best[0]: " << specs[0] << std::endl;
        ftyp bestEval = specs[0].eval;
        for( long long loop=1 ; true ; loop++ ) {
            for( size_t i=bests ; i<specs.size() ; i++ ) {
                cross( specs[ pDist(rnd) ] , specs[ pDist(rnd) ] , specs[ i ] , rnd , bDist  );
                evalSpec( specs[i] , backpack , items );
            }
            for( size_t i=1 ; i<specs.size() ; i++ ) {
                if( rnd() % mutation == 0 ) {
                    mutationSpec( specs[i] , rnd );
                    evalSpec( specs[i] , backpack , items );
                }
            }
            std::sort(specs.begin(), specs.end(), cmpSpec);
            if( bestEval < specs[0].eval || time(NULL) - lastTime > 180 ) {
                bestEval = specs[0].eval;
                std::cout << (time(NULL)-start) << "s; best[" << loop << "]: " << specs[0] << std::endl;
                lastTime = time(NULL);
            }
        }
    }
    catch( std::exception &e ) {
        std::cout << "Wystapił błąd: " << e.what() << std::endl;
    }
    return 0;
}

 

Comments

Wow, tego się nie spodziewałem. Dziękuję bardzo będę siedział i czytał co tam się dokładnie dzieje, w razie pytań a na pewno takie będą mogę się z tobą skontaktować przez prywatną wiadomość?

---

Chętnie pomogę jeśli będę mógł. Dodam na razie tylko  tyle, że te wersje które wgrałem nie są standardowe, w podręcznikach takich nie widziałem, nie mają klasycznej ruletki ani funkcji przystosowania. Te wersje są za to prostsze w implementacji, szybsze i u mnie zwykle szybciej znajdowały lepsze rozwiązanie. Algorytm krzyżowania także nie jest typowy, ale taki w podręcznikach można znaleźć :)

Tutaj jest po prostu pula rodziców, podaje się ile osobników ma mieć szansę na wydanie potomstwa. Z ruletką złożoność jest kwadratowa, gdy się da miliony osobników to algorytm widocznie spowalnia. W moich implementacjach jest sortowanie, ma złożonoś NLogN, to też mocno spowalnia przy milionach osobników, ale mniej.

Nie sprawdzałem czy poprawnie liczy, ale jak Ci się podoba, to wrzucę jeszcze z jednym udoskonaleniem i poprawkami :) W problemie plecakowym można znaleźć dobre rozwiązanie algorytmem zachłannym. Okazuje się że w algorytmie genetycznym też warto posortować itemy po stosunku wartości do wagi, poniważ losowo zainicjowane bity w genotypie osobników z większym prawdopodobieństwem wybierają itemy właśnie z początku. Przyspieszenie dzięki temu jest ogromne - ale to nadal heurystyka, nie ma gwarancji że rozwiązanie bedzie optymalne.

---

@mmarszik,

prog.cpp:20:38: warning: dynamic exception specifications are deprecated [-Wdeprecated-dynamic-exception-spec]
    virtual const char* what() const throw(){
                                     ^~~~~~~
prog.cpp:20:38: note: use 'noexcept' instead
    virtual const char* what() const throw(){
                                     ^~~~~~~
                                     noexcept
prog.cpp:17:36: warning: constructor parameter 'swhat' shadows the field 'swhat' of 'MyException' [-Wshadow-field-in-constructor]
    MyException( const char *const swhat ) : swhat(swhat) {
                                   ^
prog.cpp:14:23: note: previous declaration is here
    const std::string swhat;
                      ^
prog.cpp:150:37: warning: zero as null pointer constant [-Wzero-as-null-pointer-constant]
        const int start = (int)time(NULL);
                                    ^~~~
                                    nullptr
/opt/local/libexec/llvm-9.0/lib/clang/9.0.0/include/stddef.h:84:18: note: expanded from macro 'NULL'
#    define NULL __null
                 ^
prog.cpp:150:27: warning: use of old-style cast [-Wold-style-cast]
        const int start = (int)time(NULL);
                          ^    ~~~~~~~~~~
prog.cpp:154:19: warning: implicit conversion changes signedness: 'const int' to
      'std::__1::discard_block_engine<std::__1::subtract_with_carry_engine<unsigned long long, 48, 5, 12>, 389, 11>::result_type'
      (aka 'unsigned long long') [-Wsign-conversion]
        Trnd rnd( seed );
             ~~~  ^~~~
prog.cpp:160:30: warning: implicit conversion turns floating-point number into integer: 'ftyp' (aka 'double') to 'const int'
      [-Wfloat-conversion]
        const int mutation = getMutation();
                  ~~~~~~~~   ^~~~~~~~~~~~~
prog.cpp:184:35: warning: implicit conversion changes signedness: 'const int' to 'std::__1::vector<Spec, std::__1::allocator<Spec>
      >::size_type' (aka 'unsigned long') [-Wsign-conversion]
        std::vector<Spec>   specs(size);
                            ~~~~~ ^~~~
prog.cpp:186:29: warning: implicit conversion changes signedness: 'int' to 'std::__1::vector<Spec, std::__1::allocator<Spec>
      >::size_type' (aka 'unsigned long') [-Wsign-conversion]
            randSpec( specs[i] , rnd, bDist , items );
                      ~~~~~ ^
prog.cpp:187:29: warning: implicit conversion changes signedness: 'int' to 'std::__1::vector<Spec, std::__1::allocator<Spec>
      >::size_type' (aka 'unsigned long') [-Wsign-conversion]
            evalSpec( specs[i] , backpack, items);
                      ~~~~~ ^
prog.cpp:192:14: warning: 'long long' is incompatible with C++98 [-Wc++98-compat-pedantic]
        for( long long loop=1 ; true ; loop++ ) {
             ^
prog.cpp:193:27: warning: implicit conversion changes signedness: 'const int' to 'size_t' (aka 'unsigned long') [-Wsign-conversion]
            for( size_t i=bests ; i<specs.size() ; i++ ) {
                        ~ ^~~~~
prog.cpp:194:31: warning: implicit conversion changes signedness: 'std::__1::uniform_int_distribution<int>::result_type' (aka 'int')
      to 'std::__1::vector<Spec, std::__1::allocator<Spec> >::size_type' (aka 'unsigned long') [-Wsign-conversion]
                cross( specs[ pDist(rnd) ] , specs[ pDist(rnd) ] , specs[ i ] , rnd , bDist  );
                       ~~~~~  ^~~~~~~~~~
prog.cpp:194:53: warning: implicit conversion changes signedness: 'std::__1::uniform_int_distribution<int>::result_type' (aka 'int')
      to 'std::__1::vector<Spec, std::__1::allocator<Spec> >::size_type' (aka 'unsigned long') [-Wsign-conversion]
                cross( specs[ pDist(rnd) ] , specs[ pDist(rnd) ] , specs[ i ] , rnd , bDist  );
                                             ~~~~~  ^~~~~~~~~~
prog.cpp:198:29: warning: implicit conversion changes signedness: 'const int' to 'unsigned long long' [-Wsign-conversion]
                if( rnd() % mutation == 0 ) {
                          ~ ^~~~~~~~
prog.cpp:204:50: warning: zero as null pointer constant [-Wzero-as-null-pointer-constant]
            if( bestEval < specs[0].eval || time(NULL) - lastTime > 180 ) {
                                                 ^~~~
                                                 nullptr
/opt/local/libexec/llvm-9.0/lib/clang/9.0.0/include/stddef.h:84:18: note: expanded from macro 'NULL'
#    define NULL __null
                 ^
prog.cpp:206:36: warning: zero as null pointer constant [-Wzero-as-null-pointer-constant]
                std::cout << (time(NULL)-start) << "s; best[" << loop << "]: " << specs[0] << std::endl;
                                   ^~~~
                                   nullptr
/opt/local/libexec/llvm-9.0/lib/clang/9.0.0/include/stddef.h:84:18: note: expanded from macro 'NULL'
#    define NULL __null
                 ^
prog.cpp:207:33: warning: zero as null pointer constant [-Wzero-as-null-pointer-constant]
                lastTime = time(NULL);
                                ^~~~
                                nullptr
/opt/local/libexec/llvm-9.0/lib/clang/9.0.0/include/stddef.h:84:18: note: expanded from macro 'NULL'
#    define NULL __null
                 ^
prog.cpp:207:28: warning: implicit conversion loses integer precision: 'time_t' (aka 'long') to 'int' [-Wshorten-64-to-32]
                lastTime = time(NULL);
                         ~ ^~~~~~~~~~
prog.cpp:12:7: warning: 'MyException' has no out-of-line virtual method definitions; its vtable will be emitted in every translation
      unit [-Wweak-vtables]
class MyException : public std::exception {
      ^

 

---

Oczywiście że mi się podoba! O sortowaniu to szczerze sam by nie pomyślał, ale mam już pierwsze pytanko może głupie ale jaki jest cel linii typedef double ftyp, wiem co robi typedef, albo przynajmniej tak mi się wydaje i jedynym zastosowaniem jakie znam to zasłonięcie jakiejś skomplikowanej nazwy albo komendy inną prostszą, tak więc tutaj po prostu żeby skrócić doubla?

---

Przedefiniowanie niektórych typow podsawowych zwykle wpisuję odruchowo w kodzie :) W tym programie poglądowym to nie ma znaczenia. Zaleta jest taka, że (przynajmniej w założeniu) można zmienić double na float, albo na long double i zobaczyć jak program działa po zmianie :)

Sortowanie itemów to taka sztuczka, podobna jak sortowanie osobników zamiast ruletki, dzięki temu program znajduje o wiele szybciej rozwiązanie.

Pozdrawiam

---

W sumie racja o tym nie pomyślałem, sprytne dziękuję bardzo. W weekend będę czytał co się dokładnie dzieje w kodzie, i jeśli to nie problem będę pisał. Dziękuje bardzo i najprawdopodobniej  do usłyszenia!

---

Cieszę się że mogłem pomóc, jak coś to pisz śmiało.

---

@mokrowski,
Jak w gcc włączyć te ostrzeżenia? Nie mam ani jednego, nawet konwersji z double na int mi nie pokazało. Kompiluję tak:

g++ -Wall -Wextra -pedantic -std=c++11 -O3 main.cpp -o genetic

Nie mam ani jednego warninga.

Pozdrawiam

---

clang++ -Weverything

.. i wyłączenie zbędnych ostrzeżeń. Np:

-Wno-missing-noreturn -Wno-padded -Wno-c++98-compat

.. tu dobrać do projektu.

Dodatkowo sanityzacja, cppcheck, clang-tidy, valgrind, iwyu, clang-format...