毕业论文遗传算法有哪些

遗传算法GA 遗传算法： 旅行商问题(traveling saleman problem,简称tsp)：已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图 g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商问题(dij≠dji,,任意i,j=1,2,3，…,n)。若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且记tn+1= t1，则旅行商问题的数学模型为：min l=σd(t(i),t(i+1)) （i=1,…,n）旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。遗传算法：初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)).评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=alpha*(1-alpha).^(i-1) 。[随机规划与模糊规划]选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1,…、从区间(0,pop-size)中产生一个随机数r；step3、若qi-1#include<>templateclass Graph{ public: Graph(int vertices=10) { n=vertices; e=0; } ~Graph(){} virtual bool Add(int u,int v,const T& w)=0; virtual bool Delete(int u,int v)=0; virtual bool Exist(int u,int v)const=0; int Vertices()const{return n;} int Edges()const{return e;} protected: int n; int e;};templateclass MGraph:public Graph{ public: MGraph(int Vertices=10,T noEdge=0); ~MGraph(); bool Add(int u,int v,const T& w); bool Delete(int u,int v); bool Exist(int u,int v)const; void Floyd(T**& d,int**& path); void print(int Vertices); private: T NoEdge; T** a;};templateMGraph::MGraph(int Vertices,T noEdge){ n=Vertices; NoEdge=noEdge; a=new T* [n]; for(int i=0;iMGraph::~MGraph(){ for(int i=0;ibool MGraph::Exist(int u,int v)const{ if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge)return false; return true;}templatebool MGraph::Add(int u,int v,const T& w){ if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]!=NoEdge){ cerr<<"BadInput!"<bool MGraph:delete(int u,int v){ if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge){ cerr<<"BadInput!"<void MGraph::Floyd(T**& d,int**& path){ d=new T* [n]; path=new int* [n]; for(int i=0;ivoid MGraph::print(int Vertices){ for(int i=0;ivoid main(){ cout<<"请输入该图的节点数："<>vertices; MGraph b(vertices,noEdge); cout<<"请输入u,v,w:"<>u>>v>>w; while(w!=noEdge){ //u=u-1; (u-1,v-1,w); (v-1,u-1,w); cout<<"请输入u,v,w:"<>u>>v>>w; } (vertices); int** Path; int**& path=Path; float** D; float**& d=D; (d,path); for(int i=0;i>V[n]; } for(n=0;n<55;n++){ for(i=0;i0&&j>i+1&&j