模拟退火-遗传算法 34省会城市TSP问题python代码

在原有传统的遗传算法上进行改进，加入了精英主义和模拟退火的方法（比较简单），但算法的效率极高，相比之前大有改观。

# -*- coding: utf-8 -*-

import random
import math

SCORE_NONE = -1

class Life（object）:
      “““个体类“““
      def __init__（self aGene = None）:
            self.gene = aGene
            self.score = SCORE_NONE

class GA（object）:
      “““遗传算法类“““
      def __init__（self aCrossRate aMutationRage aLifeCount aGeneLenght aMatchFun ）:
            #lambda作为一个表达式，定义了一个匿名函数
            self.croessRate = aCrossRate
            self.mutationRate = aMutationRage
            self.lifeCount = aLifeCount
            self.geneLenght = aGeneLenght
            self.matchFun = aMatchFun                 # 适配函数
            self.lives = []                           # 种群
            self.best = None                          # 保存这一代中最好的个体
            self.generation = 1
            self.crossCount = 0
            self.mutationCount = 0
            self.bounds = 0.0                        # 适配值之和，用于选择是计算概率
            self.mean = 1.0                           # 适配值平均值
            self.initPopulation（）


      def initPopulation（self）:
            “““初始化种群“““
            self.lives = []
            for i in range（self.lifeCount）:
                  gene = [ x for x in range（self.geneLenght） ] 
                  random.shuffle（gene）#用来对一个元素序列进行重新随机排序
                  life = Life（gene）
                  self.lives.append（life）


      def judge（self）:
            “““评估，计算每一个个体的适配值“““
            self.bounds = 0.0
            self.best = self.lives[0]
            for life in self.lives:
                  life.score = self.matchFun（life）
                  self.bounds += life.score
                  if self.best.score < life.score:
                        self.best = life
            self.mean=self.bounds/self.lifeCount


      def cross（self parent1 parent2）:
            “““交叉“““
            n=0
            while 1:
                  newGene = []

                  index1 = random.randint（0 self.geneLenght - 1）#用于生成一个指定范围内的整数
                  index2 = random.randint（index1 self.geneLenght - 1）
                  tempGene = parent2.gene[index1:index2]   # 交叉的基因片段
                  p1len = 0
                  for g in parent1.gene:
                        if p1len == index1:
                              newGene.extend（tempGene）     # 插入基因片段
                              p1len += 1
                        if g not in tempGene:
                              newGene.append（g）
                              p1len += 1
                  if （self.matchFun（Life（newGene）） > max（self.matchFun（parent1）self.matchFun（parent2）））:
                        self.crossCount += 1
                        return newGene
                  # else:
                  #       rate = random.random（）
                  #       if rate < math.exp（-100 / math.sqrt（self.generation））:
                  #             self.crossCount += 1
                  #             return newGene
                  if （n>100）:
                        self.crossCount += 1
                        return newGene
   

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2017-12-28 13:40  GA-TSP\
     文件        5328  2017-12-13 03:30  GA-TSP\GA.py
     文件        2895  2017-12-06 09:40  GA-TSP\TSP_GA.py