01 背包问题——遗传算法

一种仿生(?)的模拟优化算法。

Reference:

https://www.cnblogs.com/heaad/archive/2010/12/23/1914725.html

http://blog.csdn.net/v_july_v/article/details/6132775

遗传算法的0-1背包问题(c语言).doc

具体内容参考资料已经讲得很详细了,我就不再赘述了。

注意遗传算法是一种随机算法,需要适当地选择参数与迭代次数才能尽可能地保证答案准确性。

代码实现(较长):


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<ctime>

using namespace std;

inline void set_file_IO(string);
inline void close_IO(void);
inline void work(void);

int main(void) {
    #ifndef ONLINE_JUDGE
        set_file_IO("Genetic-Algorithm");
    #endif
    //ios::sync_with_stdio(false);
    work();
    #ifndef ONLINE_JUDGE
        close_IO();
    #endif
    return 0;
}

inline void set_file_IO(string name) {
    freopen((name + ".in" ).c_str(), "r", stdin );
    freopen((name + ".out").c_str(), "w", stdout);
}

inline void close_IO(void) {
    fclose(stdin);
    fclose(stdout);
}

const int nSize = 500, mSize = 10000;

const int popSize = 200, maxGen = 10000;
const double pc = 0.618, pm = 0.03, alpha = 1;

int dataProfit[nSize], dataWeight[nSize];
int num, contain, gen = 0;

inline double rand_real(void) {
    return (rand() + 0.) / RAND_MAX;
}

inline bool exercise(const double probability) {
    return rand_real() <= probability;
}

inline int mutate_op(const int raw) {
    return exercise(pm) ^ raw;
}

struct individual {
    unsigned int chromosome[nSize];
    double fitness, weight;
    //unsigned int parent1, parent2, cross;
   
    void calc(void) { // fitness & weight
        weight = fitness = 0;
        for (int i=0; i<num; ++i) {
            weight += chromosome[i] * dataWeight[i];
            fitness += chromosome[i] * dataProfit[i];
        }
        if (weight > contain) {
            fitness -= alpha * (weight - contain);
        }
    }
   
    void initialize(void) {
        //parent1 = parent2 = cross = 0;
        for (int i=0; i<num; ++i) {
            chromosome[i] = rand() & 1;
        }
        calc();
    }
   
    void mutate(void) {
        for (int i=0; i<num; ++i) {
            chromosome[i] = mutate_op(chromosome[i]);
        }
        calc();
    }
};

inline individual crossover(const individual a, const individual b) {
    individual res;
    int crossPos = exercise(pc)? (rand()%(num-1)): num-1;
    for (int i=0; i<=crossPos; ++i) {
        res.chromosome[i] = a.chromosome[i];
    }
    for (int i=crossPos+1; i<num; ++i) {
        res.chromosome[i] = b.chromosome[i];
    }
    res.calc();
    //res.cross = crossPos;
    return res;
}

struct population {
    individual ind[popSize];
    double fitSum, fitMin, fitMax;
    unsigned int posMin, posMax;
   
    void count(void) {
        fitSum = fitMin = fitMax = ind[0].fitness;
        posMin = posMax = 0;
       
        for (int i=1; i<popSize; ++i) {
            fitSum += ind[i].fitness;
            const double tmp = ind[i].fitness;
            if (tmp > fitMax) {
                fitMax = ind[i].fitness;
                posMax = i;
            }
            if (tmp < fitMin) {
                fitMin = ind[i].fitness;
                posMin = i;
            }
        }
    }
   
    void report(void) {
        cout << "The generaion is: " << gen << endl;
        cout << "The best individual's chromosome is:" << endl;
        for (int i=0; i<num; ++i) {
            cout << ind[posMax].chromosome[i] << " ";
        }
        cout << endl;
        cout << "The population's max fitness is: " << (int)ind[posMax].fitness << endl;
        cout << "The knapsack weight is: " << (int)ind[posMax].weight << endl;
        cout << endl;
    }
   
    void initialize(void) {
        for (int i=0; i<popSize; ++i) {
            do {
                ind[i].initialize();
            } while (ind[i].weight > contain);
        }
        count();
    }
   
    int select(void) {
        double wheelPos = rand_real() * fitSum, partSum = 0;
        for (int i=0; i<popSize; ++i) {
            partSum += ind[i].fitness;
            if (partSum >= wheelPos) {
                return i;
            }
        }
        return 0;
    }
   
    population generate(void) {
        population res;
        for (int i=0; i<popSize; ++i) {
            do {
                const int mate1 = select(), mate2 = select();
                res.ind[i] = crossover(ind[mate1], ind[mate2]);
                res.ind[i].mutate();
            } while (res.ind[i].weight > contain);
        }
        res.count();
        return res;
    }
} pop, newPop;

inline void read(void) {
    cin >> num >> contain;
    for (int i=0; i<num; ++i) {
        cin >> dataWeight[i];
    }
    for (int i=0; i<num; ++i) {
        cin >> dataProfit[i];
    }
    /*
    cin >> contain >> num;
    for (int i=0; i<num; ++i) {
        cin >> dataWeight[i] >> dataProfit[i];
    }
    */

}

inline void work(void) {
    srand(time(0));
    read();
    pop.initialize();
    //pop.report();
    for (gen=1; gen<maxGen; ++gen) {
        if (gen % 100 == 0) {
            //cerr << "Processing Generation " << gen << endl;
        }
        if (gen % 100 == 0) {
            srand(time(0));
        }
        newPop = pop.generate();
        if (newPop.fitMax < pop.fitMax) {
            newPop.ind[newPop.posMin] = pop.ind[pop.posMax];
            newPop.count();
        } else if (newPop.fitMax > pop.fitMax) {
            //newPop.report();
        }
        pop = newPop;
    }
    cout << pop.fitMax << endl;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注