Environment
- Python 3.6.5 Anaconda
Code
I’ve changed variable and constant names significantly. Additionally, I’ve modified the init_parcel function to automatically generate items without needing a test file. Furthermore, in the eval_fit function, I’ve added output for the total weight along with the fitness.
The explanation of the eval_fit function in the book referred to it as the fitness calculation function, but fitness here refers to the total value. In the following code, I return both the total weight and the value as fitness.
|
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 |
import math import random import copy from itertools import product MAX_VALUE = 100 N = 30 WEIGHT_LIMIT = N * MAX_VALUE / 4 POOL_SIZE = 30 LAST_GENERATION = 50 MUTATION_RATE = 0.01 SEED = 32767 parcel = [[0 for i in range(2)] for j in range(N)] def rndn(n): return random.randint(0, n - 1) def init_parcel(): global parcel parcel = [ [ random.randint(1, MAX_VALUE), random.randint(1, MAX_VALUE) ] for j in range(N) ] def mating(pool, ng_pool): roulette = [0 for i in range(POOL_SIZE)] total_fitness = 0 for i in range(POOL_SIZE): weight, roulette[i] = eval_fit(pool[i]) total_fitness += roulette[i] for i in range(POOL_SIZE): while True: mama = select_p(roulette, total_fitness) papa = select_p(roulette, total_fitness) if mama != papa: break crossing( pool[mama], pool[papa], ng_pool[i * 2], ng_pool[2 * i + 1]) def eval_fit(gene): """ Calculate total value. Return 0 for overweight. """ value = 0 weight = 0 for pos in range(N): weight += parcel[pos][0] * gene[pos] value += parcel[pos][1] * gene[pos] if weight >= WEIGHT_LIMIT: return weight, 0 return weight, value def select_p(roulette, total_fitness): acc = 0 ball = rndn(total_fitness) for i in range(POOL_SIZE): acc += roulette[i] if acc > ball: break return i def crossing(m, p, c1, c2): cp = rndn(N) for j in range(cp): c1[j] = m[j] c2[j] = p[j] for j in range(cp, N): c2[j] = m[j] c1[j] = p[j] def mutation(ng_pool): for i, j in product(range(POOL_SIZE * 2), range(N)): if random.random() < MUTATION_RATE: if ng_pool[i][j] == 0: ng_pool[i][j] = 1 else: ng_pool[i][j] = 0 def select_ng(ng_pool, pool): total_fitness = 0 roulette = [0 for i in range(POOL_SIZE * 2)] acc = 0 for i in range(POOL_SIZE): total_fitness = 0 for c in range(POOL_SIZE * 2): _, roulette[c] = eval_fit(ng_pool[c]) total_fitness += roulette[c] ball = rndn(total_fitness) acc = 0 for c in range(POOL_SIZE * 2): acc += roulette[c] if acc > ball: break pool[i] = copy.deepcopy(ng_pool[c]) def print_p(pool): total_fitness = 0 best_fit = 0 for i in range(POOL_SIZE): weight, fitness = eval_fit(pool[i]) if fitness > best_fit: best_fit = fitness elite = i print( pool[i], " fitness =", fitness, "weight =", weight) total_fitness += fitness print(elite, best_fit, total_fitness / POOL_SIZE) if __name__ == "__main__": random.seed(SEED) pool = [ [rndn(2) for i in range(N)] for j in range(POOL_SIZE) ] ng_pool = [ [0 for i in range(N)] for j in range(POOL_SIZE * 2) ] generation = 0 init_parcel() for generation in range(LAST_GENERATION): print(generation, 'generation') mating(pool, ng_pool) mutation(ng_pool) select_ng(ng_pool, pool) print_p(pool) |
There are still areas where further changes can be made, such as encapsulating the items into a class, but this is a basic implementation.
Keep in mind that the combinations of items are generated multiple times, and there’s no guarantee that the score will always improve from the previous generation. However, the average score tends to increase over generations.
Since this algorithm progresses randomly rather than in a planned manner, there may be cases where the ng_pool contains only one candidate due to specific numeric conditions. In such cases, it may lead to an error termination. If there are no candidates at all, it will be impossible to exit the loop.
