基因演算法(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()