## 环境设定
import numpy as np
import matplotlib.pyplot as plt
from deap import base, tools, creator, algorithms
import random
params = {
'font.family': 'serif',
'figure.dpi': 300,
'savefig.dpi': 300,
'font.size': 12,
'legend.fontsize': 'small'
}
plt.rcParams.update(params)
from copy import deepcopy
# 问题定义
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) #最小化问题
creator.create('Individual', list, fitness=creator.FitnessMin)
# 个体编码
edges = [
'1,2', '1,3', '1,4', '1,5', '1,6',
'2,3', '2,4', '2,5', '2,6',
'3,4', '3,7', '3,8', '3,9', '3,10',
'4,5', '4,7', '4,8', '4,9', '4,10',
'5,6', '5,7', '5,8', '5,9', '5,10',
'6,7', '6,8', '6,9', '6,10',
'7,8', '7,11', '7,12',
'8,9', '8,11', '8,12',
'9,10', '9,11', '9,12',
'10,11', '10,12',
'11,12'
]
def generateSFromEdges(edges):
'''用关联表存储图，从提供的边集中生成与各个节点i相邻的节点集合Si
输入：edges -- list, 其中每个元素为每个节点上的边，每个元素均为一个str 'i,j'
输出：nodeDict -- dict, 形如{'i':[j,k,l]}，记录从每个节点能到达的其他节点
'''
nodeDict = {}
for edge in edges:
i,j = edge.split(',')
if not i in nodeDict:
nodeDict[i] = [int(j)]
else:
nodeDict[i].append(int(j))
# 无向图中(i,j)与(j,i)是相同的
if not j in nodeDict:
nodeDict[j] = [int(i)]
else:
nodeDict[j].append(int(i))
return nodeDict
def eligibleEdgeSet(nodeDict, i):
'''辅助函数，生成从节点i出发的所有边(i,j)
输入：nodeDict -- dict，记录每个节点能到达的其他节点
i -- 起始节点，int
输出：edgeSet -- list，记录从节点i出发可能的所有边的集合，其中每个元素为一条边，形如'i,j'的str
'''
endNodeSet = nodeDict[str(i)] # i节点的所有后续节点
