遺伝アルゴリズムで0-1リュックの問題を解決することを教えます||python実現

本例では、設定された初期クラスタの数が限られており、遺伝子突然変異が設定されていないため、得られた結果は、毎回が最適であることを保証することができず、毎回の適応度関数が終了時に収束することを保証するしかない.

# coding utf-8
import  random

x ={
    1: [10, 15],
    2: [15, 25],
    3: [20, 35],
    4: [25, 45],
    5: [30, 55],
    6: [35, 70]
}

#       
FINISH_LIMT = 0 []

#     
WEIGHT_LIMIT = 80

#      
CHROMOSOME_SIZE =6

#     
SELECT_NUMBER = 4

#          
max_last = 0

#                  
diff_last = 10000


#          
#          
def init():
    chromosomes_state1 = '100100'
    chromosomes_state2 = '101010'
    chromosomes_state3 = '010101'
    chromosomes_state4 = '101011'
    chromosomes_states = [chromosomes_state1, chromosomes_state2, chromosomes_state3, chromosomes_state4]
    return chromosomes_states


#         
#                           
def fitness(chromosomes_states):
    fitnesses = []
    for chromosomes_state in chromosomes_states:
        value_sum = 0
        weight_sum = 0
        # enumerate            ，           
        for i,v in enumerate(chromosomes_state):
            if int(v)==1:
                weight_sum += x[i+1][0]
                value_sum += x[i + 1][1]
        fitnesses.append([value_sum,weight_sum])
    return fitnesses


#                      
#                     
#                   
def is_finished(fitnesses):
    global max_last
    global diff_last
    max_current = 0
    #               
    for v in fitnesses:
        if v[1]>max_current:
            max_current = v[1]
    diff = max_current - max_last
    #      ，               
    if diff= 0:
        index -= 1
        if fitnesses[index][1] > WEIGHT_LIMIT:
            chromosomes_states.pop(index)
            fitnesses.pop(index)
    select_index = [0] * len(chromosomes_states)
    #       
    for i in range(SELECT_NUMBER):
        j = chromosomes_states.index(random.choice(chromosomes_states))
        select_index[j] += 1
    return select_index


#      
#                  ，                   
#          
def crossover(chromosomes_states,select_index):
    chromosomes_states_new = []
    tmp = chromosomes_states[:]
    index = len(chromosomes_states) - 1
    while index >= 0:
        index -= 1
        chromosomes_state = tmp.pop(index)
        for i in range(select_index[index]):
            chromosomes_state_x =random.choice(chromosomes_states)
            #              
            pos = random.choice(range(1,CHROMOSOME_SIZE-1))
            chromosomes_states_new.append(chromosomes_state[:pos]+chromosomes_state_x[pos:])
    return chromosomes_states_new


#       
chromosomes_states = init()
#        100 
n = 100
while n>0:
    n -= 1
    #      100-i       
    fitnesses = fitness(chromosomes_states)
    for i in fitnesses:
        print(i, end=' ')

    #                           
    if is_finished(fitnesses):
        break
    #   
    select_index = filter(chromosomes_states,fitnesses)
    #      
    chromosomes_states = crossover(chromosomes_states,select_index)
    print()

print()
for i in chromosomes_states:
    print(i,end=' ')