#include <cstdlib>行粗
#include <fstream>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <cassert>
using namespace std
const int DIMENSION=535//城市个数
const int PERSONS=1000//种群个数
const int crosspob=0.75//决定是否交叉的概率
const double mute=0.03//变异概率
const int iternum=100000//计划迭代次数
ofstream out("res100000.txt")
int nmutations
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
struct chrom
{
unsigned int gene[DIMENSION-1]//固定第一个城市
int fitness//该路径的长度
}//表征每个染色体特征
struct Population
{
struct chrom person[PERSONS]//有这么多个染色体
double fitsum//适应值之和
int minfit//最小适应度的下标
}//种群的喊扰一些属性
//function declare here*********************************
int select(Population* p)
bool Flip(float prob)
void Cross(unsigned int* table1,unsigned int* table2)
void Mutation(unsigned int* table)
void crossover(Population* pold,Population* pnew,int parent1,int parent2,int i)
void UpdateGen(Population* pold,Population* pnew)
void shuffle(unsigned int* table)
void ComputeFitness(Population* p,int* distance)
void InitData(Population* p,int* distance)
//function declare here*********************************
bool Flip(float pro)
{
float temp
temp=(float)rand()/(float)RAND_MAX
if(temp<=pro)
return true
else
return false
}
int find(unsigned int* table,unsigned int a,int start,int end)//返回a在数组table中郑带旦的下标
{
for(int i=starti<=endi++)
{
if(a==table[i])
return i
}
return -1
}
void exchange(unsigned int* table,int index1,int index2)
{
unsigned int temp=table[index1]
table[index1]=table[index2]
table[index2]=temp
}
void Cross(unsigned int* table1,unsigned int* table2)
//对两个基因进行交叉 *** 作，生成子代的两个基因
{
int rand1=rand()%(DIMENSION-101)+50
//assure rand1 range from 2 to DIMENSION-4,left and right side reserve at least 50 elements
int rand2=rand1
do
{
rand2=rand()%(DIMENSION-101)+50
}while(rand1==rand2)//assure rand1 differ from rand2
const int start=min(rand1,rand2)
const int end=max(rand1,rand2)
for(int i=starti<=endi++)
{
unsigned int t1=table1[i]
unsigned int t2=table2[i]
if(t1!=t2)
{
int a1=find(table1,t2,0,DIMENSION-2)
exchange(table1,a1,i)
int b1=find(table2,t1,0,DIMENSION-2)
exchange(table2,b1,i)
}
}
}
void Mutation(unsigned int* table)//依据一定概率对基因进行变异，变异 *** 作是2-opt的
{
bool mut=Flip(mute)
if(mut)//如果发生了变异
{
nmutations++
int rand1=rand()/(DIMENSION-1)
int rand2
do
{
rand2=rand()/(DIMENSION-1)
}while(rand1==rand2)
exchange(table,rand1,rand2)
}
return
}
void crossover(Population* pold,Population* pnew,int parent1,int parent2,int i)
//对群体中的两个个体杂交，生成新的个体,并将新个体保存进新的种群里
{
struct chrom* ch1=&(pnew->person[i])
struct chrom* ch2=&(pnew->person[i+1])
struct chrom* ch1_old=&(pold->person[parent1])
struct chrom* ch2_old=&(pold->person[parent2])
unsigned int* table1=ch1->gene
unsigned int* table2=ch2->gene
memcpy(table1,ch1_old->gene,sizeof(unsigned int)*(DIMENSION-1))
memcpy(table2,ch2_old->gene,sizeof(unsigned int)*(DIMENSION-1))
bool cro=Flip(crosspob)//依据交叉概率决定是否交叉
if(cro)
Cross(table1,table2)
Mutation(table1)//对交叉后的新基因进行变异
Mutation(table2)//对交叉后的新基因进行变异
}
void UpdateGen(Population* pold,Population* pnew,int* distance)
{
for(int i=0i<PERSONSi+=2)
{
int parent1=select(pold)
int parent2=select(pold)
crossover(pold,pnew,parent1,parent2,i)
}
//至此新的种群已经生成了，同时注意比较旧种群中最好适应度的个体和新种群中最好适应度的个体
ComputeFitness(pnew,distance)//计算新种群每个个体的适应度和总的适应度，最优个体
int newPopMinfit=pnew->person[pnew->minfit].fitness
int oldPopMinfit=pold->person[pold->minfit].fitness
if(oldPopMinfit<newPopMinfit)//如果旧种群的最优值优于新种群的最优值，替换新种群的最优值
{
struct chrom* ch_new=&(pnew->person[pnew->minfit])
struct chrom* ch_old=&(pold->person[pold->minfit])
unsigned int* table_new=ch_new->gene
unsigned int* table_old=ch_old->gene
memcpy(table_new,table_old,sizeof(unsigned int)*(DIMENSION-1))
ch_new->fitness=ch_old->fitness
}
}
int select(Population* p)//从人口中选择合适的人来交配
{
double average_fit=(double)p->fitsum/(double)PERSONS
int i
while(true)
{
i=rand()%PERSONS
struct chrom* ch1=&(p->person[i])
double ratio=(double)ch1->fitness/average_fit
double prob=1.0/(1.0+ratio)
bool sel=Flip(prob)
if(sel)
break
}
return i
}
void shuffle(unsigned int* table)
{
int num=2000
while(num--)
{
int rand1=rand()%(DIMENSION-1)
int rand2
do{
rand2=rand()%(DIMENSION-1)
}while(rand1==rand2)
exchange(table,rand1,rand2)
}
}
void ComputeFitness(Population* p,int* distance)
{
int i,j
int minvalue=10000000
double fitsum=0.0
for(i=0i<PERSONSi++)
{
struct chrom* ch1=&(p->person[i])
unsigned int *table=ch1->gene
int length=distance[ (table[0]-1) ]+ distance[ (table[DIMENSION-2]-1)]
cout<<length<<endl
//先将第一个城市到基因序列的第一个城市和最后的城市的距离计算在内
for(j=0j<DIMENSION-2j++)
{
int di=table[j]-1
int dj=table[j+1]-1
assert(di!=dj)
length+=distance[di*DIMENSION+dj]
}
ch1->fitness=length
fitsum+=ch1->fitness
if(ch1->fitness<minvalue)
{
minvalue=ch1->fitness
p->minfit=i
}
cout<<minvalue<<endl
}
p->fitsum=fitsum
cout<<fitsum<<endl
}
void InitData(Population* p,int* distance)
{
srand(time(NULL))
int i
unsigned int table[DIMENSION-1]
for(i=0i<DIMENSION-1i++)
table[i]=i+2
for(i=0i<PERSONSi++)
{
struct chrom* ch1=&(p->person[i])
shuffle(table)
memcpy(ch1->gene,table,sizeof(unsigned int)*(DIMENSION-1))
}
ComputeFitness(p,distance)
}
int main()
{
const double PI=3.1415926
const double RRR=6378.388
float* cord=new float[DIMENSION*2]
int* distance=new int[DIMENSION*DIMENSION]
//*******************读取城市坐标************************************//
ifstream in("ali535.tsp")
char str[256]
int i,j
for(i=0i<7i++)
in.getline(str,256)
for(i=0i<DIMENSIONi++)
{
int index
float x,y
in>>index>>x>>y
int dx = (int) x
float err_x = x- dx
float latitude = PI * (dx + 5.0 * err_x/ 3.0) / 180.0
int dy= (int)y
float err_y= y- dy
float longitude = PI * (dy + 5.0 * err_y/ 3.0) / 180.0
cord[i*2]= latitude
cord[i*2+1]= longitude
}
in.close()
//*******************读取城市坐标************************************//
//*******************计算城市距离矩阵******************************//
for(i=0i<DIMENSIONi++)
for(j=0j<DIMENSIONj++)
{
if(i==j)
distance[i*DIMENSION+j]=0
else
{
float xi,xj,yi,yj
xi=cord[i*2]xj=cord[j*2]yi=cord[i*2+1]yj=cord[j*2+1]
double q1 = cos( yi-yj )
double q2 = cos( xi-xj )
double q3 = cos( xi+xj)
int dij = (int)(RRR * acos( 0.5*( (1.0+q1)*q2 - (1.0-q1)*q3 ) ) + 1.0)
distance[i*DIMENSION+j]= dij
}
}
//*******************计算城市距离矩阵******************************//
Population* oldPop=new Population
Population* newPop=new Population
InitData(oldPop,distance)
long int start,end
start=time(NULL)
for(int k=1k<=iternumk++)
{
UpdateGen(oldPop,newPop,distance)
Population* temp=oldPop
oldPop=newPop
newPop=temp
int dis_tour=oldPop->person[oldPop->minfit].fitness
out<<"第 "<<k<<" 代的最小距离＝ "<<setprecision(10)<<dis_tour<<endl
}
end=time(NULL)
out<<"总的变异次数＝ "<<nmutations<<" 总共耗时＝ "<<end-start<<" 秒"<<endl
delete [] distance
delete [] cord
delete oldPop
delete newPop
return 0
}
蚁群算法又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。神经丛漏网络
思维学普遍认为，人类大脑的思维分为抽象（逻辑）思维、形象（直观）思维和灵感（顿悟）思维三种基本方式。
逻辑性的思维是指根据逻辑规则进行推理的过程；它先将信息化成概念，并用符号表示，然后，根据符号运算按串行模式进行逻辑推理；这一过程可以写成串行的指令，让计算机执行。然而，直观性的思维是将分布式存储的信息综合起来，结果是忽然间产生想法或解决问题的办法。这种思维方式的根本之点在于以下两点:1.信息是通过神经元上的兴奋模式分布储在网链带络上2.信息处理渗唤烂是通过神经元之间同时相互作用的动态过程来完成的。
人工神经网络就是模拟人思维的第二种方式。这是一个非线性动力学系统，其特色在于信息的分布式存储和并行协同处理。虽然单个神经元的结构极其简单，功能有限，但大量神经元构成的网络系统所能实现的行为却是极其丰富多彩的。
神经网络的研究内容相当广泛，反映了多学科交叉技术领域的特点。目前，主要的研究工作集中在以下几个方面：
（1）生物原型研究。从生理学、心理学、解剖学、脑科学、病理学等生物科学方面研究神经细胞、神经网络、神经系统的生物原型结构及其功能机理。
（2）建立理论模型。根据生物原型的研究，建立神经元、神经网络的理论模型。其中包括概念模型、知识模型、物理化学模型、数学模型等。
（3）网络模型与算法研究。在理论模型研究的基础上构作具体的神经网络模型，以实现计算机馍拟或准备制作硬件，包括网络学习算法的研究。这方面的工作也称为技术模型研究。
（4）人工神经网络应用系统。在网络模型与算法研究的基础上，利用人工神经网络组成实际的应用系统，例如，完成某种信号处理或模式识别的功能、构作专家系统、制成机器人等等。
纵观当代新兴科学技术的发展历史，人类在征服宇宙空间、基本粒子，生命起源等科学技术领域的进程中历经了崎岖不平的道路。我们也会看到，探索人脑功能和神经网络的研究将伴随着重重困难的克服而日新月异。
遗传算法，是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）