#!usr/bin/perl
use OpenGL qw/ :all /;
my %city=( 0=> "A;200:100",
1=> "B;200:300",
2=> "C;500:300",
3=> "D;500:100",
4=> "E;600:200",
5=> "F;300:100",
6=> "G;100:200",
7=> "H;300:200",
8=> "K;300:500",
9=> "L;100:500",
10=>"M;200:600",
11=>"N;800:100",
12=>"O;120:500",
13=>"P;21:100",
14=>"Q;20:40",
15=>"I;33:201",
16=>"R;300:50",
17=>"J;10:50",
18=>"X;20:60",
19=>"T;80:10",
20=>"W;120:50",
21=>"Z;210:10",
22=>"J;500:500",
23=>"X;420:500",
24=>"T;210:400",
25=>"W;400:220",
26=>"Z;431:346"
);
$gja=900;
$gje=800;
#--the constants for the population
my $population=80;
my @v=keys %city;
my $chromosom_length=@v;
my $best=0,$best_2=0;$worst=-1,$worst_2=-1;
my $gen=0;
my @random_numbers=split(/-/,rand_nums($generations));
my $maxk=0;
my %chromosome;
my %children;
my %cache;
#======================================
sub rand_nums {
my %local_cache;
my ($length) = @_;
my $serial = int(rand($length));
$local_cache{$serial} = 1;
for (2..$length) {
my $num = int(rand($length));
redo if exists $local_cache{$num};
$local_cache{$num} = 1;
$serial .= "-$num";
}
rand_nums($length) if exists $cache{$serial};
$cache{$serial}=1;
return $serial;
}
sub init_population{
$clr=$_[0];
for ($i=0;$i<$population;$i++){
@r=split(/-/,rand_nums($clr));
$chromosome{$i}=join('-',@r);
print "$chromosome{$i} \n";
}
}
sub fitnes{
@chromo=split(/-/,$_[0]);
my $r=0;
for($i=0;$i<$chromosom_length-1;$i++){
$pos=$chromo[$i];
@d=split(/;/,$city{$pos});
$name=$d[0];
@t=split(/:/,$d[1]);
$x1=$t[0];
$y1=$t[1];
#next;
$pos=$chromo[$i+1];
@d=split(/;/,$city{$pos});
$name=$d[0];
@t=split(/:/,$d[1]);
$x2=$t[0];
$y2=$t[1];
#--------------------
$t1=$x2-$x1;
$t2=$y2-$y1;
#print "$t1 $t2\n";
$dis=sqrt(($t1*$t1)+($t2*$t2));
$r+=$dis;
}
return ($r);
}
sub evaluate_population{
foreach (sort{$a<=>$b} keys %chromosome) {
if ((fitnes($chromosome{$_})<=fitnes($chromosome{$best}))){
$best_2=$best;
$best=$_;
}
if ((fitnes($chromosome{$_})>=fitnes($chromosome{$worst}))){
$worst_2=$worst;
$worst=$_;
}
}
}
#-----helper-
sub clean{
@chromo=split(/-/,$_[0]);
@crosoverDNA=split(/-/,$_[1]);
my $nr=0;
foreach(@chromo){
my $vl=$_;
foreach(@crosoverDNA){
$chromo[$nr]="H" if($_==$vl);
}
$nr++;
}
return(join('-',@chromo));
}
sub replace_holes{
my %lcache;
my $clr=$_[1];
@chromo_vector=split(/-/,$_[0]);
foreach(@chromo_vector){
$lcache{$_}+=1;
}
my @rand_vec=split(/-/,rand_nums($clr));
my $nr=0;
my @t;
#gjenerimi i nr te ndryshem
for($i=0;$i<$clr;$i++){
push @t,$rand_vec[$i] if!(exists $lcache{$rand_vec[$i]});
}
#-------
foreach(@chromo_vector){
if($_ eq 'H'){
$chromo_vector[$nr]=shift(@t);
}
$nr++;
}
return(join('-',@chromo_vector));
}
sub mutate{
@individ=split(/-/,$_[0]);
my $crl=$_[1];
$c1=int(rand(time()*$$) % $crl);
$c2=int(rand(time()*$$^2) % $crl);
$t=$individ[$c1];
$individ[$c1]=$individ[$c2];
$individ[$c2]=$t;
return(join('-',@individ));
}
sub kopjo{
@v= split(/-/,$_[0]);
$p1=$_[1];
$p2=$_[2];
my @r;
for($i=$p1;$i<=$p2;$i++){
push @r,$v[$i];
}
return(join('-',@r));
}
#------------
sub reproduct_population{
print_population();
print "gjenerate $gen best $chromosome{$best} best fitnes nr $best:".fitnes($chromosome{$best})."\n";
my $fathernr=int(rand(time()^$$*2)) % $population;
#my $fathernr=$best;
#my $mothernr=rand($$*time^5) % $population;
#my $mothernr=$best_2;
foreach(sort{$a<=>$b} keys %chromosome){
$mothernr=$_;
my $cnr=0;
if ($mothernr!=$fathernr){
my @father_vector=split(/-/,$chromosome{$fathernr});
my @mother_vector=split(/-/,$chromosome{$mothernr});
my $nr=0,@temp;
if(int(rand(time()^$$)) % 100<20){
do{
$c1=int(rand(time^$$)) % $chromosom_length;
$c2=int(rand(2*$$*time())) % $chromosom_length;
#$c2=$chromosom_length;
}while(($c1==0)||($c2==0));
if ($c2>$c1){
$cx=&kopjo(join('-',@father_vector),$c1,$c2);
$cy=&kopjo(join('-',@mother_vector),$c1,$c2);
$father_c =&clean(join('-',@father_vector),$cy);
$mother_c =&clean(join('-',@mother_vector),$cx);
$c1x=&kopjo($father_c,0,$c1-1);
$c2x=&kopjo($father_c,$c2+1,$chromosom_length);
$c1y=&kopjo($mother_c,0,$c1-1);
$c2y=&kopjo($mother_c,$c2+1,$chromosom_length);
$child_1=$c1x."-".$cy."-".$c2x;
$child_2=$c1y."-".$cx."-".$c2y;
}else{
$cx=&kopjo(join('-',@father_vector),$c2,$c1);
$cy=&kopjo(join('-',@mother_vector),$c2,$c1);
$father_c =&clean(join('-',@father_vector),$cy);
$mother_c =&clean(join('-',@mother_vector),$cx);
$c1x=&kopjo($father_c,0,$c2-1);
$c2x=&kopjo($father_c,$c1+1,$chromosom_length);
$c1y=&kopjo($mother_c,0,$c2-1);
$c2y=&kopjo($mother_c,$c1+1,$chromosom_length);
$child_1=$c1x."-".$cy."-".$c2x;
$child_2=$c1y."-".$cx."-".$c2y;
}
$child1=&replace_holes($child_1,$chromosom_length);
$child2=&replace_holes($child_2,$chromosom_length);
if (fitnes($child1)<fitnes($child2)){
if(! exists $cache{$child1}){
$chromosome{$_}=$child1 if(fitnes($child1)<fitnes($chromosome{$_}));
$cache{$child1}=1;
}
}else{
if(! exists $cache{$child2}){
$chromosome{$_}=$child2 if(fitnes($child2)<fitnes($chromosome{$_}));
$cache{$child2}=1;
}
}
}#crosover
if(int(rand(time()^$$)) % 100<101){
$m=mutate($chromosome{$_},$chromosom_length);
if((!exists $cache{$m})&&(fitnes($m)<fitnes($chromosome{$_}))){
$chromosome{$_}=$m;
$cache{$m}=1;
}
}
}
}
#print_population();
}
sub print_population{
foreach (sort{$a<=>$b} keys %chromosome) {
print "$_ -> $chromosome{$_} \n";
}
}
sub ourPrintString
{
my ($font, $str) = @_;
my @c = split '', $str;
for(@c)
{
glutBitmapCharacter($font, ord $_);
}
}
sub vizato_reth{
$NPOINTS=24;
$TWOPI=2*3.14159268;
$STEP=$TWOPI/$NPOINTS;
glBegin(GL_LINE_LOOP);
for($angle=0;$angle<$TWOPI;$angle+=$STEP){
glVertex2f(0.5 * cos($angle), 0.5* sin($angle));
}
glEnd();
}
sub print_interpretation_of_vector{
@v=split(/-/,$chromosome{$best});
$nr=0;
glLoadIdentity();
glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);#Aktivizo Bufferat
#glTranslatef(10,10,1);#pergatit matricen e Skenes per futje te nje elementi ose transformimi
glPushMatrix();
glBegin(GL_LINE_LOOP);#start drawing a line loop
foreach(@v){
my $q1=$_;
foreach(@v){
my $q2=$_;
@data=split(/;/,$city{$q1});
@cord=split(/:/,$data[1]);
$x=$cord[0];
$y=$cord[1];
glColor3f(0.3,0.3,0.3);
glVertex2f("$x.0","$y.0");
@data=split(/;/,$city{$q2});
@cord=split(/:/,$data[1]);
$x=$cord[0];
$y=$cord[1];
glVertex2f("$x.0","$y.0");
}
}
#glVertex2f(100.0,100.0);
#glVertex2f(100.0,200.0);
glEnd();
glPopMatrix();
glPushMatrix();
glBegin(GL_LINE_LOOP);#start drawing a line loop
$r="";
foreach(@v){
@data=split(/;/,$city{$_});
@cord=split(/:/,$data[1]);
$x=$cord[0];
$y=$cord[1];
glColor3f(0,1,0);
glVertex2f("$x.0","$y.0");
$r.='glRasterPos2i('.$x.','.$y.');ourPrintString(GLUT_BITMAP_HELVETICA_12,":'.$data[0].'");';
}
#glVertex2f(100.0,100.0);
#glVertex2f(100.0,200.0);
glEnd();
eval($r);
glPopMatrix();
glutPostRedisplay();
glutSwapBuffers();#Ruhen ndryshimet ne framebuffer
return($r);
}
sub init{
glClearColor(0,0,0,0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0,$gja,0,$gje,-1.0,1.0);
glDisable(GL_DEPTH_TEST);#Aktivizo sensin e thellesise
glMatrixMode(GL_MODELVIEW);
}
sub idle{
$gen++;
&reproduct_population();
&evaluate_population();
}
#----main simualtion
&init_population($chromosom_length);
&evaluate_population();
#&print_population();
glutInit();#rutine inicializimi e glut
glutInitWindowSize($gja,$gje); #permasat e dritares
glutInitWindowPosition(10,10);#pozicione ne dritaren e sistemit operativ
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);#Aktivizo bufferin e thellesise
glutCreateWindow("OPENTSP");
init();
glutDisplayFunc(\&print_interpretation_of_vector);#funksioni callback qe vizaton ekranin
glutIdleFunc(\&idle);#Kur ske cfare te besh aktivizo kete funksion
glutSetOption(GLUT_ACTION_ON_WINDOW_CLOSE,GLUT_ACTION_GLUTMAINLOOP_RETURNS);
glutMainLoop();#ripersrit ciklin