# 關於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.