Multicriteria-Knapsack-Problem-using-Genetic-Algorithm/Main.py at master · soumi1805/Multicriteria-Knapsack-Problem-using-Genetic-Algorithm · GitHub

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
import random

MAX_WEIGHT = 12
MAX_VOLUME= 10

VAL = 0
WEIGHT = 1
VOLUME=2

NUM_GENERATIONS = 10000
NUM_TESTS = 5

GENERATION_SIZE = 10
CROSSOVER_RATE = 0.7
MUTATION_RATE = 0.01

CHROMOSOME_SIZE = 0

inventory = []

chromosomes = []
fitness = []
sum_fitness = 0

START_POP_WITH_ZEROES = False

### LOGISTIC FUNCTIONS ###
def read_file():
    global CHROMOSOME_SIZE

    with open("Inventory") as f:
        lines = f.readlines()

    for line in lines:
        line = line.split("\t")
        inventory.append((line[0], line[1], line[2].replace("\n", "")))

    CHROMOSOME_SIZE = len(inventory)


def generate_base_generation():
    chromosome = ""
    for i in range(GENERATION_SIZE):
        for j in range(CHROMOSOME_SIZE):
            chromosome += str(random.randint(0, 1))
        chromosomes.append(chromosome)
        chromosome = ""
    print("Initial Population:",chromosomes)


def test_fitness():
    global fitness
    global sum_fitness

    weight = 0
    value = 0
    volume=0

    for i in range(GENERATION_SIZE):
        chromosome = chromosomes[i]
        for j in range(CHROMOSOME_SIZE):
            if chromosome[j] is "1":
                weight += int(inventory[j][WEIGHT])
                value += int(inventory[j][VAL])
                volume +=int(inventory[j][VOLUME])

        if weight>MAX_WEIGHT:
            fitness.append(0)
        elif volume > MAX_VOLUME:
            fitness.append(0)
        else:
            fitness.append(value)
        weight = 0
        value = 0
        volume=0
    sum_fitness = sum(fitness)


### GENETIC FUNCTIONS ###
def pick_parent(): #returm index of the parent
    r1 = random.randint(0, 9)
    r2 = random.randint(0, 9)
    r3 = random.randint(0, 9)
    # print(r1,r2,r3)
    vr1 = fitness[r1]
    vr2 = fitness[r2]
    vr3 = fitness[r3]
    return fitness.index(max(vr1, vr2, vr3))


def crossover(index1, index2):
    curr_rate = random.random()

    if curr_rate < CROSSOVER_RATE:
        #i = random.randint(0, CHROMOSOME_SIZE - 1)
        i=int(CHROMOSOME_SIZE/2) #crosing over the half
        l1 = list(chromosomes[index1])
        l2 = list(chromosomes[index2])

        l1 = l2[:i] + l1[i:]
        l2 = l1[:i] + l2[i:]
        return "".join(l1) , "".join(l2)

    return chromosomes[index1], chromosomes[index2]


def mutate(chromosome_list):
    for i in range(GENERATION_SIZE):
        l = list(chromosome_list[i])
        for j in range(CHROMOSOME_SIZE):
            curr_rate = random.random()
            if curr_rate < MUTATION_RATE:
                l[j] = "1" if l[j] is "0" else "0"
                chromosome_list[i] = "".join(l)


def create_new_generation(index):
    global chromosomes
    global fitness

    new_generation = []

    for i in range(int(GENERATION_SIZE / 2)):
        ch1, ch2 = crossover(pick_parent(), pick_parent())
        new_generation.append(ch1)
        new_generation.append(ch2)

    mutate(new_generation)
    chromosomes = new_generation
    fitness = []
    test_fitness()
    if index % int(NUM_GENERATIONS / NUM_TESTS) == 0:
        print("this generation best fit has value of: %d\nthe chromosome is: %s\n" % (max(fitness), chromosomes[fitness.index(max(fitness))]))


### MAIN FUNCTION ###
def main():
    read_file()
    generate_base_generation()
    test_fitness()

    for i in range(NUM_GENERATIONS): #10000
        create_new_generation(i)

main()