改进的二叉树编码遗传算法及其在多旅行商中的应用.pdf.pdf

第��期总第���期�内蒙古科技与经济���.��,����������������
����年�月����������������������������������������������.�����
改进的二叉树编码遗传算法及其在多旅行商中的应用�
吕�佳,邢秋霞,陆�静�
�新乡医学院图书馆,河南新乡��������
摘�要:为了解决多人旅行商问题,文章提出了一种基于二叉树编码的改进遗传算法。将多旅行商�
问题转化为等效的���图,并将其转化成二叉树,然后进��遍历编码,再用改进的遗传算子进行算法优�
化。该算法克服了一维编码的局限性,通����真实验验证了其有效性及比普通的一位编码遗传算法更高�
的执行效率。�
关键词:遗传算法;多旅行商;二叉树编码�
中图分类号:����.���文献标识码:��文章编号:����—������������一��������
旅行商问题���������������������������,以�系,分别用“�”和“�”来表示顺序关系和并列关系�
下称����是一个典型的组合优化难题,它在许多领�最后通过访问方案图转化为二叉树的算法及合并操�
域都有着非常广泛的应用,属于典型的��问题���。�作的算法建立起编码二叉树。�
���问题是指:有�个城市,要求旅行商到达每个�二叉树只表示节点间的逻辑结构,物理存储可�
城市各�次,且仅�次,并回到起点,且要求旅行路线�用邻接矩阵和链表,但是这些存储方式用于染色体�
最短�而多旅行商问题是指�个旅行商从同�个城�编码都不利于遗传算子操作。所以我们需要先对二�
市�或不同城市�出发,分别走一条旅行路线,使得每�叉树进行后续遍历,得到一个序列,然后对此序列进�
个城市有且仅有�个旅行商经过�出发城市除外�,�行染色体编码。�
且总路程最短。��.�适应值函数�
在实际问题中,限制单个旅行商的费用�或路�在遗传算法中,个体被遗传到下一代群体中的�
程�具有一定的实际意义,因此有必要对所有旅行商�概率是由该个体的适应度决定的。但是由于规模的�
路程最大值最小化的����问题进行研究。为了有�多样性和个体适应度的差异不同,有些遗传算法收�
效地解决单个旅行商路程最小、距离对称或者非对�敛得很快,有些收敛得很慢,所以,如何把握个体适�
称的����问题,笔者用改进的遗传算法�进行优�应度的尺度也是一个重要问题���。如何把个体适应�
化,引入了二叉树编码和双适应度函数,同时在变异�度进行适当的放大或者缩小是提高个体之间竞争性�
算子进行改进,以便确定每个城市由哪个旅行商经�和多样性的关键所在,适应值函数设计不当有可能�
过以及各个旅行商的行走路线,在各个旅行商行走�导致很多问题的出现。�
完后,使路程最大的那个旅行商的路程最小。�由于优化目标为最小化路程或费用值,因此。令�
�遗传算法设计�目标函数作指数变换得到适应值函数:�—�����一目�
笔者在此提出了改进的混合遗传算法的具体步�× ��;�,�为正实数。�
骤,通过在编码方案和算子的改进以希望得到局部��.��选择�
和全局寻优的更好结合,同时在收敛性和运行效率�在随机联赛选择过程中是随机选取几个个体适�
上有