關於Python 程式碼_1

幫幫忙,解釋一下這要做什麼?

1.Create an initial population

import random, copy

sample_chrm = range(1,10) # a feasible solution

init_population = [ ] # an empty list random.seed(0)

population_size = 5

for i in xrange( population_size ):

new_chrm = copy.copy( sample_chrm )

random.shuffle( new_chrm)

init_population.append( new_chrm )

2.Evaluate fitness values

The cost matrix of travel between each pair of cities can be created like below.

cost_matrix = []# an empty list

cost_matrix.append([0,0,0,0,0,0,0,0,0,0])

cost_matrix.append([0,0,1,5,6,9,2,3,7,8])

cost_matrix.append([0,1,0,8,6,2,4,7,9,5])

cost_matrix.append([0,5,8,0,3,2,7,6,8,9])

cost_matrix.append([0,6,6,3,0,9,7,4,1,5])

cost_matrix.append([0,9,2,2,9,0,1,4,7,3])

cost_matrix.append([0,2,4,7,7,1,0,7,4,1])

cost_matrix.append([0,3,7,6,4,4,7,0,8,3])

cost_matrix.append([0,7,9,8,1,7,4,8,0,1])

cost_matrix.append([0,8,5,9,5,3,1,3,1,0])

For the given chrm (chromosome), the total cost of travel can be calculated like

following example code.

chrm = [4, 1, 5, 6, 9, 2, 3, 7, 8]

cost = 0

last_city = chrm[0]

for current_city in chrm:

cost += cost_matrix[last_city][current_city]

last_city = current_city

The high cost value means low fitness. Thus we cannot use the cost value

directly as a fitness value. One can use various methods to calculate fitness values

from cost values.

1 個解答

評分
  • 1 0 年前
    最佳解答

    這看起來是用基因演算法來解Traveling Salesman的問題。

    1.Create an initial population

    import random, copy

    # 總共有九個城市,所以染色體的長度是九

    # 初始化為 [1, 2, 3, .... 9]; 注意是以1為基準

    sample_chrm = range(1,10) # a feasible solution

    init_population = [ ] # an empty list random.seed(0)

    population_size = 5

    # Initialize五個解答(染色體)並隨機排列

    for i in xrange( population_size ):

    new_chrm = copy.copy( sample_chrm )

    random.shuffle( new_chrm)

    init_population.append( new_chrm )

    ================================

    2.Evaluate fitness values

    # 初始化每個城市間的距離(旅行的耗費)

    # 注意Index 0 在這裡不用,因為上面以1

    The cost matrix of travel between each pair of cities can be created like below.

    cost_matrix = []# an empty list

    cost_matrix.append([0,0,0,0,0,0,0,0,0,0])

    cost_matrix.append([0,0,1,5,6,9,2,3,7,8])

    cost_matrix.append([0,1,0,8,6,2,4,7,9,5])

    cost_matrix.append([0,5,8,0,3,2,7,6,8,9])

    cost_matrix.append([0,6,6,3,0,9,7,4,1,5])

    cost_matrix.append([0,9,2,2,9,0,1,4,7,3])

    cost_matrix.append([0,2,4,7,7,1,0,7,4,1])

    cost_matrix.append([0,3,7,6,4,4,7,0,8,3])

    cost_matrix.append([0,7,9,8,1,7,4,8,0,1])

    cost_matrix.append([0,8,5,9,5,3,1,3,1,0])

    For the given chrm (chromosome), the total cost of travel can be calculated like

    following example code.

    # 這裡舉例說明如何計算某個特定路徑(染色體)的耗費

    # 以此為基本,可以計算某個染色體的Fitness

    # 既然目的是要找出最短路徑,耗費越少的越 Fit (符合要求)

    # 所以,Fitness Function 可以 return 耗費的倒數,或是其負數值

    chrm = [4, 1, 5, 6, 9, 2, 3, 7, 8]

    cost = 0

    last_city = chrm[0]

    for current_city in chrm:

    cost = cost_matrix[last_city][current_city]

    last_city = current_city

    The high cost value means low fitness. Thus we cannot use the cost value

    directly as a fitness value. One can use various methods to calculate fitness values

    from cost values.

還有問題?馬上發問,尋求解答。