Autor Wątek: ALGORYTM MRÓWKOWY- problem  (Przeczytany 3986 razy)

Offline TMKii

  • Użytkownik

# Wrzesień 18, 2009, 21:23:28
witam.

poniżej jest kod algorytmu mrówkowego, więc w sumie mam pytanie skierowane do osób które mają jako takie pojęcie jak to cholerstwo działa....
prawdopodobnie jest to algorytm prawie poprawnie zaimplementowany, wiem że kod jest bardzo nieoptymalny ale to akurat nie jest istotne bo za chwilę będę to poprawiał....
w załączniku pliki na których program się bawi
żeby to odpalić proponuję skopiować cały kod, skompilować pod vs 2008
i wywołać tak:
mrowkojad.exe url
gdzie url to ścieżka do folderu w której są dwa zzipowane pliki, np:
mrowkojad.exe trasa\

no ale do rzeczy, w czym problem....
otóż nie wiem czemu ale na trasie na której z powodu odległości (1000), ilość feromonu powinna drastycznie spadać ta rośnie szybciej niż na trasach najlepszych
tablice:
lewo dół- ilość feromonów na krawędzi [nr_kolumna] -[nr_wiersz]
prawo góra- odległości pomiędzy  [nr_wiersz]-[nr_kolumna]

za uwagi dziękuję...


// mrowkojad.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <ctime>
#include <time.h>
#include <iomanip>

using namespace std;
#define MAX_ROZMIAR 20

//funkcja wyświetla helpa programu
void help();

//funkcja wyświetlajaca graf

void wyswietl(double graf_wyswietlany[MAX_ROZMIAR][MAX_ROZMIAR]);


//funkcja przeprowadzajaca wszystkie obliczenia programu
int * mrowkojad(double graf_pom[MAX_ROZMIAR][MAX_ROZMIAR], double graf[MAX_ROZMIAR][MAX_ROZMIAR], double rozmiar_grafu, double rozmiar_colony,double ant_hp,double start ,double stop ,double colony,double alfa,double beta ,double parowanie, int ile_losowych, int *tablica_losowa);


int main(int argc, char * argv[])
{
int wynik;
system("cls");
srand(NULL);
//sprawdzenie liczby parametrów, te nadprogramowe są ignorowane
if(argc<=1)
{
cout<<"Nie podoano wszystkich wymaganych parametrow"<<endl;
help();
return 0;
};
string graf_url, parametry_url;
//pierwszy parametr to sciezka do folderu, nastepuje jej wczytanie
istringstream sciezka(argv[1]);


sciezka>>graf_url;
parametry_url=graf_url;
//uzupelnienie sciezki do pliku zawierajacego graf oraz do pliku zawierajacego parametry
graf_url+="graf.txt";
parametry_url+="parametry.txt";
//pruba otwarcia obydwu plików
ifstream plik1, plik2;
plik1.open(parametry_url.c_str(), ios::in);
plik2.open(graf_url.c_str(), ios::in);
//jeżeli nastąpiło otwarcie obydwu plików podjęcie pruby przetwarzania danych
if((plik1.good()==1)&&(plik2.good()==1))
{
cout<<" Wszystkie pliki zostaly znalezione \n Parametry wywolania sa poprawne \n Teraz nastapi odczyt plikow"<<endl;
double parametry[10];//tablica zawierajaca parametry algorytmu
int j=0;
bool i=0;
while(!plik1.eof()&&(!i))
{
plik1>>parametry[j];
j++;
if(j==10)
i=1;
}
plik1.close();
if((j!=10)||!plik1.eof())
{
cout<<"Zla ilosc parametrow algorytmu"<<endl;
help();
return 0;
}

cout<<"Rozmiar grafu               \t : \t"<<parametry[0]-1<<endl;
cout<<"Ilosc mrowek w koloni       \t : \t"<<parametry[1]<<endl;
cout<<"Punkty zycia mrowek:        \t : \t"<<parametry[2]<<endl;
cout<<"Punkt startowy w grafie     \t : \t"<<parametry[3]<<endl;
cout<<"Punkt koncowy w grafie      \t : \t"<<parametry[4]<<endl;
cout<<"Ilosc wypuszczonych kolonii \t : \t"<<parametry[5]<<endl;
cout<<"Wspolczynnik alfa           \t : \t"<<parametry[6]<<endl;
cout<<"Wspolczynnik beta           \t : \t"<<parametry[7]<<endl;
cout<<"wspolczynnik parowania p    \t : \t"<<parametry[8]<<endl;
cout<<"Poczatkowa ilosc feromonu   \t : \t"<<parametry[9]<<endl;

double graf[MAX_ROZMIAR][MAX_ROZMIAR];
memset(graf, 0, sizeof(double)*MAX_ROZMIAR*MAX_ROZMIAR);
j=(parametry[0]*(parametry[0]-1))/2;
cout<<"Teraz nastapi pruba wczytania "<<j<<"  dlugosci krawedzi grafu"<<endl;
int k=0;
while(!plik2.eof())
{
int p,pp,r;
pp=1;
for(p=0; p<(parametry[0]-1); p++)
{
for(r=pp; r<(parametry[0]); r++)
{
if(!plik2.eof())
{
plik2>>graf[p][r];
if(graf[p][r]>0)
graf[r][p]=parametry[9];
k=k+1;
}

}
pp++;
}
}
plik2.close();
cout<<"j:"<<j<<endl;
cout<<"k:"<<k<<endl;
if(k!=j)
{
cout<<"Niezgodna z parametrami liczba krawedzi grafu"<<endl;
help();
return 0;
}
wyswietl(graf);
cout<<endl;
///
system("PAUSE");
double graf_pom[MAX_ROZMIAR][MAX_ROZMIAR];
memset(graf_pom, 0, sizeof(double)*MAX_ROZMIAR*MAX_ROZMIAR);
mrowkojad(graf_pom,graf, parametry[0],parametry[1],parametry[2],parametry[3],parametry[4],parametry[5],parametry[6],parametry[7],parametry[8],0,0);

///tutaj wstawic funkcje



}
// jeżeli nie udało się otworzyć jakiegoś z plików to program jest kończony
else
{
cout<<"Nie odnaleziono wszystkich potrzebnych do dzialania programu plikow\n";
help();
}

//system("PAUSE");
return 0;
}



int * mrowkojad(double graf_pom[MAX_ROZMIAR][MAX_ROZMIAR], double graf[MAX_ROZMIAR][MAX_ROZMIAR], double rozmiar_grafu, double rozmiar_colony,double ant_hp,double start ,double stop ,double colony,double alfa,double beta ,double parowanie, int ile_losowych, int *tablica_losowa)
{

int i,j,r,k,z,y,n,pom;
double szansa=0, czynnik_l=0, mianownik=0,los;
bool znacznik=1;
bool zakleszczenie, powtorka;
int ** mrowki;
try                   // próba tworzenia tablicy wskaźników
{
mrowki = new int *[(int)rozmiar_colony];
}
catch(bad_alloc)
{
cout << "Brak miejsca na utworzenie tablicy."<<endl;
return 0;
}
for (i=0; i<rozmiar_colony; i++)

try                  // próba tworzenia dynamicznych tablic liczb
{
mrowki[i] = new int [(int)(ant_hp+3)];
}
    catch(bad_alloc)
{
cout << "Brak miejsca na utworzenie tablicy."<<endl;
return 0;
}
 
    cout <<"Proba utworzenia dynamicznych tablic mrowek zakonczona powodzeniem"<<endl;

for(i=0; i<rozmiar_colony; i++)
{
mrowki[i][0]=0;
mrowki[i][1]=0;
mrowki[i][2]=(int)start;
for(j=3; j<=(ant_hp+2); j++)
{
mrowki[i][j]=0;
}
}

for(k=0; k<colony; k++)
{
for(i=0; i<rozmiar_colony; i++)
{
mrowki[i][0]=0;
mrowki[i][1]=0;
mrowki[i][2]=(int)start;
for(j=3; j<=(ant_hp+2); j++)
{
mrowki[i][j]=-1;
}
}
//cout<<"++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ \n";
//cout<<"Wypuszczono kolonie "<<k<<"\n";
for(r=2; r<(ant_hp+2); r++)
{
memset(graf_pom, 0, sizeof(double)*MAX_ROZMIAR*MAX_ROZMIAR);
//cout<<"\t To jest tura nr \t"<< r-1<< "\t dla koloni \t"<<k<<"\n";
for(j=0; j<(int)rozmiar_colony; j++)
{
znacznik=1;
powtorka=0;
//cout<<"\n\n\t\t Teraz skacze mrowka nr "<<j<<"\t \n";
//liczenie czynnika_l
czynnik_l=0;
for(z=0; z<(int)rozmiar_colony; z++)
{
if(mrowki[z][0]>0)
czynnik_l=czynnik_l+(1/((double)mrowki[z][0]));
}
if(mrowki[j][1]!=1)
{
//zaczynamy obliczać mianownik
pom=mrowki[j][r];
for(z=pom; z<(int)rozmiar_grafu;z++)
{
if((graf[pom][z])>0)
{
mianownik=mianownik+(pow(graf[pom][z], alfa))*(1/(pow(graf[z][pom],beta)));
}
}//koniec pętli obiegu poziomego
for(z=pom; z>0; z--)
{
if(graf[z][pom]>0)
{
mianownik=mianownik+pow(graf[z][pom], alfa)*(1/(pow(graf[pom][z],beta)));
}
}//koniec pętli obiegu pionowego
//kończymy obliczać mianownik
//cout<<mianownik<<" to mianownik"<<endl;
while(znacznik!=0)
{
// a teraz skaczemy po krawędziach
for(z=(int)pom; z<((int)rozmiar_grafu);z++) //prubujemy skoczyć poziomo
{
//for(n=2; ((n<((int)(ant_hp+3)))||(!z)); n++)
//{
// cout<<"-znacznik"<<znacznik<<endl;
// cout<<"-z:"<<z<<endl;
// cout<<"-mrowka "<<j<<"w pamieci nr: "<<n<<" ma" <<mrowki[j][n]<<endl;
// if(((int)mrowki[j][n])==z)
// {
// znacznik=0;
// }
//}

//for(n=2; n<(int)(ant_hp+2); n++)
//{
// if((int)mrowki[j][n]==z+1)
// powtorka=1;
//}


if(graf[pom][z]>0)
{
szansa=(pow(graf[z][pom],alfa))*(1/(pow(graf[pom][z],beta)))/mianownik;

//cout<<"szansa to: "<<szansa<<"\n";
los=(rand()%1000000);
los=los/1000000;
//cout<<"los to: "<<los<<"\n" ;
if(((szansa>los)&&znacznik)&&(!powtorka))
{
mrowki[j][r+1]=z;
znacznik=0;
mrowki[j][0]=mrowki[j][0]+(int)graf[pom][z];
graf_pom[z][pom]=czynnik_l;
//cout<< j<<" skoczyla z "<< pom<<" do "<<z <<" i przebiegla juz poziomo "<<mrowki[j][0]<<"\n";
if(z==(int)stop)
{
mrowki[j][1]=1;
//cout<<"\a";
}
}
}
}
for(z=(int)pom; z>0;z--) //prubujemy skoczyć pionowo
{
//for(n=2; ((n<((int)(ant_hp+3)))||(!z)); n++)
//{
// cout<<"+znacznik"<<znacznik<<endl;
// cout<<"+z:"<<z<<endl;
// cout<<"+mrowka "<<j<<"w pamieci nr: "<<n<<" ma" <<mrowki[j][n]<<endl;
// if(((int)mrowki[j][n])==z)
// {
// znacznik=0;
// }

//}
//TUTAJ
if(graf[z][pom]>0)
{
szansa=(pow(graf[pom][z],alfa))*(1/(pow(graf[z][pom],beta)))/mianownik;
  los=(rand()%10000);
los=los/10000;
if((szansa>los)&&znacznik&&(!powtorka))
{
//((int)(rand()/(RAND_MAX+1))%1000);(rand()%1000)
mrowki[j][r+1]=z;
znacznik=0;
mrowki[j][0]=mrowki[j][0]+(int)graf[z-1][pom-1];
graf_pom[pom][z]=czynnik_l;
//cout<< j<<" skoczyla z "<< pom<<" do "<< z<<" i przebiegla juz pionowo "<<mrowki[j][0]<<"\n";
if(z==(int)stop)
{
mrowki[j][1]=1;
// cout<<"\a";
}
}
}
}
//koniec pruby skakania
}





}//koniec if'a który sprawdza czy mrówka na mecie
//wyswietl(graf_pom);
for(z=0; z<(int)rozmiar_grafu; z++)
{
for(y=0; y<z; y++)
{
graf[z][y]=graf[z][y]*(1-parowanie)+graf_pom[z][y];
}
}
} // koniec obiegu pętli dla wszystkich mrówek w turze


}// koniec pętli dla tury
//cout<<"------------------------------------------------------------ \n";
}//koniec pętli dla koloni

wyswietl(graf);

return 0;
}


void help()
{
cout<<"\n To jest pomoc programu \n";
cout<<"Program zlicza za pomoca algorytmu koloni mrowek najkrotsza"<<endl;
cout<<"droge w grafie pomiedzy dwoma wyznaczonymi wierzcholkami \n"<<endl;
cout<<"*************************************************"<<endl;
cout<<" \t argumety wywolania programu"<<endl;
cout<<" \t ===== \t ===================="<<endl;
cout<<" \t arg \t przeznaczenie"<<endl;
cout<<" \t ===== \t ===================="<<endl;
cout<<" \t 1 \t sciezka do folderu zawierajacego pliki z danymi"<<endl;
cout<<" \t 2 \t tryb pracy programu, 1 -tryb normalny, 2- tryb testowy"<<endl<<endl;
cout<<"*************************************************"<<endl;
cout<<"W folderze z danymi powinny znalezc sie dwa pliki :"<<endl;
cout<<"******************             \t ***************"<<endl;
cout<<"plik z parametrami             \t parametry.txt "<<endl;
cout<<"plik z macierza opisujaca graf \t graf.txt"<<endl;
cout<<"Szczegoly co do ich konstrukcji znajduja sie w pliku pomocy."<<endl;
cout<<"*************************************************"<<endl;
cout<<endl<<endl<<"Wyniki pracy programu znajduja sie w  folderze"<<endl;
cout<<"w ktorym zostaly przyszykowane dane do zbadania, w pliku wynik.txt" <<endl<<endl;
}
void wyswietl(double graf_wyswietlany[MAX_ROZMIAR][MAX_ROZMIAR])
{
int i,j;
for(i=0; i<MAX_ROZMIAR;i++)
{
for(j=0; j<MAX_ROZMIAR; j++)
{
if(graf_wyswietlany[i][j]>0)
cout<<setw(15)<<graf_wyswietlany[i][j];
else
cout<<setw(15)<<".";
}
cout<<endl;
}
}
« Ostatnia zmiana: Październik 06, 2009, 00:44:39 wysłana przez TMKii »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline TMKii

  • Użytkownik

# Wrzesień 18, 2009, 22:08:35
echm..... muszę przyznać że ślepy jestem... żeby przez prawie 3 godziny zastanawiać się nad tak banalnym problemem....
więc problem już nie aktualny.... ale jak ktoś chce się tym cholerstwem pobawić to zapraszam do zabawy....... :]
no i oczywiście można to wykorzystać po dodaniu brakującej funkcjonalności jako ciekawy algorytm sztucznej inteligęcji dla wyszukiwania najkrutszej trasy....


=====
bu ... jednak sobie ze wszystkim nie poradziłem....
czy jest może ktoś kto się tym algorytmem bawił i może mi doradzić jak rozwiązać taki banalny problem.... algorytm działa, tylko że z racji tego że dużo się w nim losuje....
kupa czasu jest zużywana na kolejne, nieudane próby skoków...
jak to rozwiązać?
====
no i mam jeszcze jeden problem z którym nie potrafię sobie poradzić...
a naprawdę tym razem nie potrafię wpaść na to co robię źle...
mianowicie chodzi mi o występujący dwa razy fragment kodu:
//for(n=2; ((n<((int)(ant_hp+3)))||(!z)); n++)
//{
// cout<<"+znacznik"<<znacznik<<endl;
// cout<<"+z:"<<z<<endl;
// cout<<"+mrowka "<<j<<"w pamieci nr: "<<n<<" ma" <<mrowki[j][n]<<endl;
// if(((int)mrowki[j][n])==z)
// {
// znacznik=0;
// }

w tej chwili kod w pierwszym poście jest kodem poprawionym....
czyli takim który "prawie działa"
problm polega na tym że znalezienie w zbiorze wierzchołków odwiedzonych już występującego tam wierzchołka powinno powodować pomijanie go a więc wydajnie przyspieszyć działanie algorytmu...
tymczasem mimo długich męczarni nie potrafię dojść do tego co zmieniam źle...
niby algorytm działa poprawnie, bo potrafi poprawnie wyznaczyć najkrótszą drogę w grafie w sposób poprawny ale przez ten banalny problem nie zaznacza tego tak jak bym chciał żeby to robił...
« Ostatnia zmiana: Wrzesień 19, 2009, 18:23:27 wysłana przez TMKii »

Offline klosio.neostr...

  • Użytkownik
    • Moje Stare Gierki

# Październik 02, 2009, 00:36:09
Taka mi się tylko nasunęła refleksja, że na drugi raz uporządkuj i skróć kod (usuń zakomentowany kod, podziel na funkcje w intuicyjny sposób, skróć linie do max 80 znaków, dodaj komentarze itd). Opisz również na początku, na czym polega problem i opisz ogólnie swój kod. Wtedy może ktoś ci pomoże. Sam chętnie bym ci pomógł, gdybym wszedł tego dnia na gamedev, gdyby nie bałagan powyżej. Aha, i nie pisz na początku posta, że problem już nieaktualny, bo ludzie przestają w tym miejscu czytać i wychodzą  ;D

Offline TMKii

  • Użytkownik

# Październik 06, 2009, 01:10:13
te 80 znaków to dla mnie na linijkę jednak troszkę za mało.... duży monitor to i z tego korzystam jak się da :]

kod jest opisany no ale w sumie racja... nieczytelny bo ja wiem jak on działa ale ktoś inny niekoniecznie tak więc...
funkcja mrowkojad() dostaje jako kilka parametrów, to co zwraca jest nieistotne bo to trzeba jeszcze dopracować :]
graf_pom[MAX_ROZMIAR][MAX_ROZMIAR], po chamsku kopia dużej tablicy
graf[MAX_ROZMIAR][MAX_ROZMIAR], jeszcze raz to samo
rozmiar_grafu, ile początkowych elementów tablicy jest wykorzystanych w obliczeniach (fragmęt NxN)
rozmiar_colony, ile mrówek ma kolonia
ant_hp, ile ruchów wykona mrówka (ta wartość +2 to rozmiar pojedyńczej mrówki reprezentowanej przez tablicę)
start , wierzchołek z którego mrówki wychodzą
stop , wierzchołek do którego chcą dojść
colony, ile koloni ma zostać wypuszczonych
alfa, współczynnik alfa
beta , współczynnik beta
parowanie,  o jaką część zmiejsza się wartość dolnej połowy macierzy w każdej turze
ile_losowych, nieistotne w tej chwili
*tablica_losowa, nieistotne w tej chwili


jak to działa?:
tworzymy rozmiar_colony liczbę mrówek, każda to tablica[hp+2], ant[0] to łączna długość trasy, ant[1] info czy meta czy nie;
algorytm jest powtarzany "colony" razy
dla każdej mrówki po kolei jest losowany z możliwych (sprawdzana obecna pozycja wedle indexu który jest numerem tury) dla danego wiersza tablicy, według wzoru,
jak mrówka skoczy to do graf_pom dodawany jest feromon,
jak wszystkie mrówki wykonają ruch to graf_pom dodawany do graf, zwiększony index tury
jak dojdzie do końca tur (wartość ant_hp to max wielkość tego indexu) to mrówki zerowane,

problem? zacytowany fragment kodu ( w trzecim poście)
ma sprawdzać czy wybrany obecnie element do którego będzie losowany skok występuje już na liście odiwedzonych elementów a jeśli tak to nie pozwolić na skok

tak wiem.... kod jest pisany prymitywnie ale wydaje mi się że robi to co ma robić... prawie dobrze, bo to tylko pisany na szybko prototyp był :]