蚁群算法

前一段时间有同学问我”蚁群算法”在matlab里怎么实现~~我就在网上一搜,发现有好多,就挑了篇看起来还不错的,扔给了他~~http://blog.csdn.net/hewei0241/article/details/8296789

东方不败蟑螂 2015/5/9 15:31:51
大概意思就是你编写一堆类似探路机的蚂蚁,他们会走一路丢一路的信息素,而信息素可以随时间衰弱,也可以叠加~~把这两块函数编好,让他们去跑地图就行了~一段时间后就下的一定是最短路径

        其实直到现在我也没细看那个网页,觉得差不多是这样,就跟他解释了一下~~结果这几天越想越觉得好玩~干脆自己写一个看看~~

        结果竟然写了一天~~还是对细节不太熟~~~

无标题1

 

        这个是我让5只蚂蚁在20*20的地图上来回跑跑出来的,信息素停留时间好像是3~一共跑的时间是100~

        其实我觉得蚁群算法真正的用途是弄一堆障碍什么的,来找最短路径;或是弄一些陷阱\地雷\或出边界就死这样的机制,才好玩~~~像我这个只是一个框架而已,蚂蚁怎么跑路径长度都差不多,当然会跑出来这种图形啦~~不过挺好看的~~~

        好啦~不罗嗦了~~把代码贴上来吧~~

无标题2

//point.h

class POINT{
friend class MAP;
friend class ANT;
public:

private:
int inf = 1;
};

 

//map.h

class POINT;

class MAP{
friend class ANT;
friend class ANTS;
public:
MAP(const int x,const int y);
void show();
void dec();
int t;
private:
POINT *point;
int lx, ly;
};

 

//map.cpp

#include “map.h”
#include “point.h”
#include <iostream>
#include <iomanip>

using namespace std;

MAP::MAP(const int x,const int y){
point = new POINT[x*y];
lx = x; ly = y;
}

void MAP::show(){
for (int i = 0; i < lx; i++){
for (int ii = 0; ii < ly; ii++){
cout <<setw(5)<<setiosflags(ios::left)<<point[i*ii + ii].inf;
}
cout << endl;
}
}

void MAP::dec(){
for (int i = 0; i < lx; i++){
for (int ii = 0; ii < ly; ii++){
if (point[i*ii + ii].inf > 1) point[i*ii + ii].inf–;
}
}
}

 

//ant.h

class MAP;

class ANT{
friend class ANTS;
public:

private:
MAP *map;
int inftime = 10;
int x=0, y=0;
enum directions{ up, left, right, down }direction = down;
void move();
int goalx = 19, goaly = 19;
};

 

//ant.cpp

#include “ant.h”
#include “map.h”
#include “point.h”
#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

void ANT::move(){
srand(time(NULL));int d;

if (x>0){
if (x<map->lx – 1){
if (y>0){
if (y<map->ly – 1){
d = rand() % (map->point[(x)*map->ly + (y – 1)].inf + map->point[(x-1)*map->ly+(y)].inf + map->point[(x)*map->ly+(y+1)].inf + map->point[(x+1)*map->ly+(y)].inf);
if (map->point[(x)*map->ly+(y-1)].inf) { y–; map->point[(x)*map->ly+(y-1)].inf += inftime; }
else if (d < map->point[(x)*map->ly+(y-1)].inf + map->point[(x-1)*map->ly+(y)].inf) { x–; map->point[(x-1)*map->ly+(y)].inf += inftime; }
else if (d < map->point[(x)*map->ly+(y-1)].inf + map->point[(x-1)*map->ly+(y)].inf + map->point[(x)*map->ly+(y+1)].inf){ y++; map->point[(x)*map->ly+(y+1)].inf += inftime; }
else{ x++; map->point[(x+1)*map->ly+(y)].inf += inftime; }
}
else{
d = rand() % (map->point[(x-1)*map->ly+(y)].inf + map->point[(x)*map->ly+(y-1)].inf + map->point[(x+1)*map->ly+(y)].inf);
if (d < map->point[(x-1)*map->ly+(y)].inf) { x–; map->point[(x-1)*map->ly+(y)].inf += inftime; }
else if (d < map->point[(x-1)*map->ly+(y)].inf + map->point[(x)*map->ly+(y-1)].inf) { y–; map->point[(x)*map->ly+(y-1)].inf += inftime; }
else { x++; map->point[(x+1)*map->ly+(y)].inf += inftime; }
}
}
else{
d = rand() % (map->point[(x-1)*map->ly+(y)].inf + map->point[(x)*map->ly+(y+1)].inf + map->point[(x+1)*map->ly+(y)].inf);
if (d < map->point[(x-1)*map->ly+(y)].inf) { x–; map->point[(x-1)*map->ly+(y)].inf += inftime; }
else if (d < map->point[(x-1)*map->ly+(y)].inf + map->point[(x)*map->ly+(y+1)].inf) { y++; map->point[(x)*map->ly+(y+1)].inf += inftime; }
else { x++; map->point[(x+1)*map->ly+(y)].inf += inftime; }
}
}
else if (y>0){
if (y<map->ly – 1){
d = rand() % (map->point[(x)*map->ly+(y-1)].inf + map->point[(x-1)*map->ly+(y)].inf + map->point[(x)*map->ly+(y+1)].inf);
if (d < map->point[(x)*map->ly+(y-1)].inf) { y–; map->point[(x)*map->ly+(y-1)].inf += inftime; }
else if (d < map->point[(x)*map->ly+(y-1)].inf + map->point[(x-1)*map->ly+(y)].inf) { x–; map->point[(x-1)*map->ly+(y)].inf += inftime; }
else { y++; map->point[(x)*map->ly+(y+1)].inf += inftime; }
}
else{
d = rand() % (map->point[(x-1)*map->ly+(y)].inf + map->point[(x)*map->ly+(y-1)].inf);
if (d < map->point[(x-1)*map->ly+(y)].inf) { x–; map->point[(x-1)*map->ly+(y)].inf += inftime; }
else { y–; map->point[(x)*map->ly+(y-1)].inf += inftime; }
}
}
else{
d = rand() % (map->point[(x-1)*map->ly+(y)].inf + map->point[(x)*map->ly+(y+1)].inf);
if (d < map->point[(x-1)*map->ly+(y)].inf) { x–; map->point[(x-1)*map->ly+(y)].inf += inftime; }
else { y++; map->point[(x)*map->ly+(y+1)].inf += inftime; }
}
}
else if (y>0){
if (y<map->ly – 1){
d = rand() % (map->point[(x)*map->ly+(y-1)].inf + map->point[(x+1)*map->ly+(y)].inf + map->point[(x)*map->ly+(y+1)].inf);
if (d < map->point[(x)*map->ly+(y-1)].inf) { y–; map->point[(x)*map->ly+(y-1)].inf += inftime; }
else if (d < map->point[(x)*map->ly+(y-1)].inf + map->point[(x+1)*map->ly+(y)].inf) { x++; map->point[(x+1)*map->ly+(y)].inf += inftime; }
else { y++; map->point[(x)*map->ly+(y+1)].inf += inftime; }
}
else{
d = rand() % (map->point[(x)*map->ly+(y-1)].inf + map->point[(x+1)*map->ly+(y)].inf);
if (d < map->point[(x)*map->ly+(y-1)].inf) { y–; map->point[(x)*map->ly+(y-1)].inf += inftime; }
else { x++; map->point[(x+1)*map->ly+(y)].inf += inftime; }
}
}
else{
//cout << map->point[5].inf << endl;
d = rand() % (map->point[(x)*map->ly+(y+1)].inf + map->point[(x+1)*map->ly+(y)].inf);
if (d < map->point[(x)*map->ly+(y+1)].inf) { y++; map->point[(x)*map->ly+(y+1)].inf += inftime; }
else { x++; map->point[(x+1)*map->ly+(y)].inf += inftime; }
}

if (x == goalx && y == goaly){ goalx = 0; goaly = 0; }
else if (x == 0 && y == 0){ goalx = map->lx-1; goaly = map->ly-1; }
}

 

//ants.h

class ANT;
class MAP;

class ANTS{
public:
ANTS(MAP &map,int num);
void move();
private:
ANT *ant;
int num;
};

 

//ants.cpp

#include “ants.h”
#include “ant.h”
#include “max.h”
#include <iostream>

ANTS::ANTS(MAP &mapp,int numm){
ant = new ANT[numm];
num = numm;
for (int i = 0; i < numm; i++){
ant[i].map = &mapp;
}
}

void ANTS::move(){
for (int i = 0; i < num; i++){
ant[i].move();
}
}

 

//main.cpp

#include <iostream>
#include “map.h”
#include “ants.h”

using namespace std;

int main(){
MAP map(20, 20);
ANTS ants(map,10);

for (int t = 0; t < 100000; t++){
//map.show(); cout << endl;
ants.move();
map.dec();
}

map.show(); cout << endl;

return 0;
}

 

其实大家如果细心可以发现,我在代码中预留了一个方向变量,但是却没用~~那是因为,我原来想的是让蚂蚁不走回头路,但后来真正编到move函数的时候就发现如是再加上一个方向,那就太复杂了~~不过后来细细想想,还是应该加上方向,不然蚂蚁们就很容易聚成一团了~~(其实为什么我感觉这好像是蚁群算法的固有缺陷呢?)~~~还是有时间真正研究一下蚁群算法吧~~

蚁群算法》上有4条评论

  1. Pingback引用通告: BZ编程小组 作品 | BZ编程小组

  2. Pingback引用通告: 浮点数输出 | BZ编程小组

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.