基因演算法(Genetic Algorithms)
基因演算法,其哲學理論就是達爾文那套優勝劣汰適者生存的進化理論的思想。一個種群,通過長時間的繁衍,種群的基因會向著更適應環境的趨勢進化,適應性強的個體基因被保留,後代越來越多,適應能力低個體的基因被淘汰,後代越來越少。經過幾代的繁衍進化,留下來的少數個體,就是相對能力最強的個體了。
目前用數學來導出進化模式,用亂數先産生一组亞當與夏娃初始基因排序值,再利用優生理論選出最優基, 本文選擇方法是用機率分佈的所謂輪盤法(Roulette Wheel Selection)來選擇。後續善用自然生態演變的兩種模式
,突變及交配産出最優的基因?原則上引用多組基因透過亂數來仿真突變及交配産出最優的基因? 但在虚擬環境中畢竟少了真實環境的因子,也造成基因演算法的區域性搜尋能力較差,導致單純的遺傳演算法比較費時,在進化後期搜尋效率較低。在實際應用中,遺傳演算法容易產生過早收斂的問題。
本文的函式如下:
流程圖如下:
Genetic Algorithms with python code
import numpy as np
import math
import ga
import matplotlib.pyplot as plt
chromosome_length = 33
population_size = 500
best_outputs = []
num_generations = 20
best_score_progress = [] # Tracks progress
next_population=[]
reference = ga.create_reference_solution(chromosome_length)
for generation in range(num_generations):
print("Generation : ", generation)
# Measuring the fitness of each chromosome in the population.
#fitness = ga.cal_pop_fitness(equation_inputs, testnew_population)
fitness = ga.cal_pop_fitness(xnew_population,ynew_population)
print("fitness")
print(fitness)
f_population=np.concatenate((v_population, fitness), axis=1)
print("f_population")
print(f_population)
#best_outputs.append(numpy.max(numpy.sum(testnew_population*equation_inputs, axis=1)))
best_outputs.append(np.max(fitness))
# The best result in the current iteration.
#print("Best result : ", numpy.max(numpy.sum(testnew_population*equation_inputs, axis=1)))
print("Best result : ", np.max(fitness))
#
# Selecting the best parents in the population for mating.
total_fitness=np.sum(fitness)
print("total_fitness")
print(total_fitness)
#to caculation orbaally of fitness
prob_select=fitness/total_fitness
print("prob_select")
print(prob_select)
prob_list=ga.get_probability_list(fitness)
prob_list=np.array(prob_list)
print("prob_list")
print(prob_list)
#print("relative_fitness")
#print(ga.get_probability_list)
parents=ga.roulette_wheel_pop(v_population,prob_list,10)
parents=np.array(parents)
print("Parents")
print(parents)
#parents = ga.select_mating_pool(v_population, fitness, num_parents_mating)
# print("Parents")
#print(parents)
#parents=list[parents]
parent1=ga.random_pop(parents,10)
print("Parent1")
print(parent1)
parent1=np.array(parent1)
#parent1=parent1[1][0]
#print("Parent1")
#print(parent1)
parents = parents.view([('', parents.dtype)] * parents.shape[1])
parent1 = parent1.view([('', parent1.dtype)] * parent1.shape[1])
parent=np.setdiff1d(parents,parent1).view(parents.dtype).reshape(-1, parents.shape[1])
print("Parent")
print(parent)
parent2=ga.random_pop(parent,10)
print("Parent1")
print(parent1)
print("Parent2")
print(parent2)
parent1=np.array(parent1)
parent2=np.array(parent2)
# to binary code
parent1_bin=ga.trans_binary(parent1)
parent2_bin=ga.trans_binary(parent2)
print("Parent1_bin")
print(parent1_bin)
print("Parent2_bin")
print(parent2_bin)
"""
child=(ga.breed_by_crossover(parent1_bin, parent2_bin))
chide1=child[0]
chide2=child[1]
print("chide1")
print(chide1)
print("chide2")
print(chide2)
"""
new_population=[0]
child_1, child_2 = ga.breed_by_crossover(parent1_bin, parent2_bin)
#x1=' '.join(format(child_1, 'b') for x in bytearray(child_1))
x1=child_1[0]
x1=' '.join(format(x, 'b') for x in bytearray(x1))
x3=child_1[1]
x3=' '.join(format(x, 'b') for x in bytearray(x3))
x2=child_2[0]
x2=' '.join(format(x, 'b') for x in bytearray(x2))
x4=child_2[1]
x4=' '.join(format(x, 'b') for x in bytearray(x4))
#for i in xrange(k):
# print(x1[i])
child_1=ga.rebinary(x1,x3)
#child_1.append(ga.rebinary(x3))
child_2=ga.rebinary(x2,x4)
#child_2.append(ga.rebinary(x4))
#xx1=np.array(xx1)
#xx3=np.array(xx3)
#child_1=np.array(child_1)
#child_2=np.array(child_2)
print("child_1")
print(child_1)
print("child_2")
print(child_2)
#child_1=np.concatenate(xx1,xx3)
#child_1 = child_1.view([('', child_1.dtype)] * child_1.shape[1])
#child_2 = child_2.view([('', child_2.dtype)] * child_2.shape[1])
#print("child_1")
# print(child_1)
chile_1,chile_2 = ga.breed_by_mutation(child_1,child_2)
new_population=child_1
new_population.append(child_2)
print("new_population")
print(new_population)
# Replace the old population with the new one
New_x1= ga.binaryToDecimal(child_1[:17])
New_x2= ga.binaryToDecimal(child_1[18:])
New_y1= ga.binaryToDecimal(child_2[:17])
New_y2= ga.binaryToDecimal(child_2[18:])
#New_x1= int(child_1[:18])
#New_x2= int(child_1[18:])
#New_y1= int(child_2[:18])
#New_y2= int(child_2[18:])
print("New+x1")
print(New_x1)
print("New+x2")
print(New_x2)
print("New_y1")
print(New_y1)
print("New_y2")
print(New_y2)
child_x1=-3.0+New_x1*(12.1-(-3.0))/(2**17)-1
child_x2=4.1+New_x2*(5.8-4.1)/(2**15)-1
child_y1=-3.0+New_y1*(12.1-(-3.0))/(2**17)-1
child_y2=4.1+New_y2*(5.8-4.1)/(2**15)-1
print("child_x1")
print(child_x1)
print("child_x2")
print(child_x2)
print("child_y1")
print(child_y1)
print("child_y2")
print(child_y2)
child=np.random.ranf(size=(2,2))
child[0,0]=child_x1
child[0,1]=child_x2
child[1,0]=child_y1
child[1,1]=child_y2
print("child")
print(child)
# print("child_2")
# print(child_2)
print("parent")
print(parent1[0,0])
parentn=np.random.ranf(size=(2,2))
x=parent1[0,0]
parentn[0,0]=x[0]
parentn[0,1]=x[1]
x=parent2[0,0]
parentn[1,0]=x[0]
parentn[1,1]=x[1]
# parents.append(parent2)
print("parent")
print(parentn)
new_population=np.array(new_population)
#next_poulation=ga.randomly_mutate_population(new_population,0.1)
#print("Next_population")
#print(next_population)
#new_population[parents.shape[0]:, :] = offspring_mutation
# Creating the new population based on the parents and offspring.
print("old_poulation")
print(v_population)
random_point = int(np.random.uniform(1, 7, 1))
v_population[random_point,0] = parentn[0,0]
v_population[random_point,1] = parentn[0,1]
v_population[random_point+1,0] = parentn[1,0]
v_population[random_point+1,1] = parentn[1,1]
v_population[random_point+2,0] = child[0,0]
v_population[random_point+2,1] = child[0,1]
v_population[random_point+3,0] = child[1,0]
v_population[random_point+3,1] = child[1,1]
print("new_poulation")
print(v_population)
# v_population[parents.shape[0]:, :] = child
#xnew_population=np.hsplit(v_population, 2, axis=0)
#ynew_population=np.hsplit(v_population, 2, axis=1)
num_repat=10
for i in np.arange(num_repat):
xnew_population[i]=v_population[i][0]
ynew_population[i]=v_population[i][1]
# Getting the best solution after iterating finishing all generations.
#At first, the fitness is calculated for each solution in the final generation.
fitness = ga.cal_pop_fitness(xnew_population,ynew_population)
# Then return the index of that solution corresponding to the best fitness.
best_match_idx = np.where(fitness == np.max(fitness))
f_population=np.concatenate((v_population, fitness), axis=1)
best_score=fitness[best_match_idx]
print("1st generation f_population")
print(f_population)
print("Best solution : ", v_population[best_match_idx, :])
print("Best solution fitness : ", fitness[best_match_idx])
best_score_progress.append(best_score)
plt.plot(best_score_progress)
plt.xlabel('Generation')
plt.ylabel('Best score (% target)')
plt.show()