[Matlab] 遗传算法求解TSP入门

引言主要依据《 MATLAB智能算法30个案例分析第2版》一书梳理一下如何利用遗传算法求解TSP旅行商问题以及学习遗传算法需要熟悉的MAtlab常用函数帮助季子木消化理解该知识点故撰写此文。了解遗传算法的基本原理遗传算法可以用来干什么遗传算法是现代启发式算法中的一种就是为了解决手算和计算机枚举计算不可能在短时间内得到精确解而采用的一种退而求其次得到近似最优解的进化算法进化是指在有限的迭代次数内能通过一些策略主要是概率使得随着迭代次数的增加能更快的逼近最优解。遗传算法是怎样干的1确定遗传算法染色体的编码方式首先要把实际问题用文字或图像表述的问题抽象成计算机能够识别计算的基本单元TSP问题说白了就是把n个点连成首尾相连的线段企图得到一条最短的线段如果手算的话就是n个点之间的顺序排列问题选择哪种连接的先后顺序能够使连接得到的线条最短这样就很清楚了那TSP问题最基础的运算单元就是n个点之间的顺序排布遗传算法的编码形式就可以取n个点之间的排序。遗传算法的编码方式就是整数编码染色体的长度就是城市的个数即n染色体上每一个基因位表示的就是城市的序号。2确定适应度函数3确定种群规模和迭代次数种群规模和迭代次数是相互作用的两个因素求解的问题时间复杂度高点那种群规模就多一点就是染色体的个数多一些种群规模太大的话每一次计算要付出的代价也大这时候就可以把种群规模调小的依赖较高的迭代次数来不断进化求解。4确定选择操作选择操作就是把种群中较好的离目标近的一些染色体选取出来选择的标准就是适应度函数选取染色体的个数是根据选择概率来确定的毕竟谁也说不准该每轮迭代该选取多少个合适。5哪些解是较好的依遗传算法的交叉和变异操作目的都是为了按照一定的策略使解的质量得到改善在更快的迭代次数内找到近似最优解。