Thursday, December 17, 2009

Car crash in front of my house


The responsible ran away!!!


- Pablo Rivas Perea
The University of Texas El Paso

Friday, December 11, 2009

Class notes for Math-5346

Can you see the question mark? It's funny!



- Pablo Rivas Perea
The University of Texas El Paso

Tuesday, December 08, 2009

How hard is to develop for iPhones ?

I am wondering how hard could it be to code my own app for my iPhone



- Pablo Rivas Perea
The University of Texas El Paso

Tuesday, March 24, 2009

Artificial Intelligence / Evolutionary Algorithms (1)

The Traveling salesman problem is described as follows: given a list of cities and their pairwise distances, find the shortest possible tour that visits each city exactly once. Design and implement a genetic algorithm to solve this problem.

MATLAB CODE

   1: function travelsp



   2: clear all; close all; clc;



   3: %Traveling Salesman Problem



   4: %Pablo Rivas Perea



   5: %800-40-4524



   6:  



   7: num_cit=inputdlg('Please type the number of cities','Step 1',1,{'8'});



   8: if ~isempty(cell2mat(num_cit))



   9:     num_cit=str2num(cell2mat(num_cit));



  10:     button = questdlg('How do you preffer to generate the distance matrix between cities?','Please confirm','Randomly','Manually','Randomly');



  11:     if strcmp(button,'Randomly')



  12:         points=rand(num_cit,2)*100;



  13:         dismat=zeros(num_cit);



  14:         for r=1:num_cit



  15:             for c=1:num_cit



  16:                 if c>r 



  17:                     d=sum((points(r,:)-points(c,:)).^2).^0.5;



  18:                     dismat(r,c)=d; dismat(c,r)=d;



  19:                 end



  20:             end 



  21:         end        



  22:     else



  23:         %do manual



  24:     end



  25:     %imagesc(dismat);



  26:     %initial parameters



  27:     solsnum=256;     %number of total solutions



  28:     numbits=size(dec2bin(num_cit-1),2); %minimum number of bits to represent the cities



  29:     elitism=1;      %best ranked solutions to keep



  30:     evolvesols=8;   %best ranked solutions to evolve, has to be EVEN



  31:     mincrossover=round(numbits*0.7); %round(rand*numbits);   %minimum start for crossover



  32:     maxmutations=round(numbits*0.5); %round(rand*numbits);   %maximum amount of mutations



  33:     maxiwnch=50;   %maximum iterations with no change on fitness (when to stop)



  34:     hfig = figure('Name','CS5314 - Genetic Algorithm Evolution','Numbertitle','off');



  35:     tic



  36:     %generate initial random solutions



  37:     sols={};



  38:     for n=1:solsnum



  39:         sols(1:num_cit,n)=randombinsol(num_cit,numbits);



  40:     end



  41:     fitsols=0; it=1;



  42:     %first iteration begins



  43:     contcrit=1;



  44:     while contcrit        



  45:         for n=1:solsnum



  46:             fitsols(n)=evalfitness(bin2dec(cell2mat(sols(:,n))),dismat);



  47:         end



  48:         [rsols,lowfit]=ranksols(sols,fitsols);   %ranking for posterior selection



  49:         history(it)=lowfit;



  50:         contcrit=evalstopcrit(history,maxiwnch);



  51:         path=(bin2dec(rsols(:,1))+1);



  52:         if contcrit<0



  53:             toc



  54:             fprintf('Solution found at iteration %d\n',it);



  55:             fprintf('Solution Fitness is: %f\nBest path is\n',lowfit); path



  56:             fprintf('\nPress enter to display the binary string\nBest path is\n');



  57:             pause;  rsols(:,1)



  58:             break;



  59:         end



  60:  



  61:         figure(hfig);



  62:         pts = points([path(:,1); path(1)],:);



  63:         plot(pts(:,1),pts(:,2),'.-','Color',[1 0 0]);



  64:         title(sprintf('Lowest fitness (Distance) = %1.4f, Generation = %d',lowfit,it));



  65:  



  66:         nsols=rsols(:,1:elitism);       %elitism parameter, keeps the best ranked



  67:         %offspring generation.  First evolve the best ranked



  68:         nsols(:,(elitism+1):(elitism+evolvesols))=fevolvesol(rsols, evolvesols, mincrossover, maxmutations, num_cit);



  69:         %then generate new random solutions



  70:         for n=(1+elitism+evolvesols):solsnum



  71:             nsols(1:num_cit,n)=randombinsol(num_cit,numbits);



  72:         end        



  73:         %first iteration complete, start to iterate all until fitness is



  74:         %reached  



  75:         sols=nsols;



  76:         it=it+1;



  77:     end



  78: end



  79: end



  80:  



  81: function rsol=randombinsol(ncities,nbits)



  82:     dsol=ones(ncities,1).*ncities;



  83:     n=0;



  84:     while n<ncities



  85:         cand=round(rand*(ncities-1));



  86:         if ~any(dsol==cand)



  87:             n=n+1;



  88:             dsol(n,1)=cand;



  89:         end



  90:     end



  91:     rsol=cellstr(dec2bin(dsol,nbits));



  92: end



  93:  



  94: function totdist=evalfitness(propsol,dismat)



  95:     totdist=0;



  96:     for n=1:(size(propsol,1)-1)



  97:         totdist=totdist+dismat(propsol(n)+1,propsol(n+1)+1);



  98:     end



  99:     totdist=totdist+dismat(propsol(n+1)+1,propsol(1)+1);



 100: end



 101:  



 102: function [rsols,lowfit]=ranksols(sols,fsols)



 103:     [rsols, ix]=sort(fsols,2);



 104:     lowfit=rsols(1);



 105:     rsols={};



 106:     for n=1:size(sols,2)



 107:         rsols(1:size(sols,1),n)=sols(1:size(sols,1),ix(n));        



 108:     end    



 109: end



 110:  



 111: function cont=evalstopcrit(history,maxiwnch)



 112:     cont=1;



 113:     if history(size(history,2))==0  %YES! Solution found



 114:         cont=0;



 115:     elseif size(history,2)>=maxiwnch



 116:         startpoint=size(history,2)-maxiwnch+1;



 117:         endpoint=size(history,2);



 118:         thist=history(startpoint:endpoint)-history(endpoint); %subtract the last best fitness from all



 119:         tthist=sum(thist);  %if the sum is zero means that there is no improvement



 120:         if tthist==0



 121:             cont=-1;



 122:         end



 123:     end



 124: end



 125:  



 126: function evosol=fevolvesol(rsols, total, mco, mmu, num_cit)



 127:     t1evosol={}; t2evosol={}; evosol={};



 128:     for n=1:2:total



 129:         t1evosol=rsols(:,n);



 130:         t2evosol=rsols(:,n+1);



 131:         crossol=bincrossover(t1evosol, t2evosol, mco);



 132:         mutsol=binmutation(crossol, mmu, num_cit);



 133:         evosol(1:size(mutsol,1),n)=mutsol(:,1);        



 134:         evosol(1:size(mutsol,1),n+1)=mutsol(:,2);



 135:     end



 136: end



 137: function crossol=bincrossover(sol1,sol2,minco)



 138:     %randomly selecting the point of crossover based on the minimum



 139:     pcross=round(rand*(size(sol1,1)-minco)+minco);



 140:     solt=sol1;



 141:     sol1(1:size(sol1,1)-pcross)=sol1(pcross+1:size(sol1,1));



 142:     sol1((size(sol1,1)-pcross+1):size(sol1,1))=solt(1:pcross);



 143:     solt=sol2;



 144:     sol2(1:size(sol2,1)-pcross)=sol2(pcross+1:size(sol2,1));



 145:     sol2((size(sol2,1)-pcross+1):size(sol2,1))=solt(1:pcross);    



 146:     crossol(1:size(sol1,1),1:2)=[sol1,sol2];



 147: end



 148:  



 149: function mutsol=binmutation(solpair,maxmu, num_cit)



 150:     m1=round(rand*maxmu);   %how many mutations to the first pair? Top=maxmu



 151:     for n=1:m1



 152:         pos=round(rand*(size(solpair,1)-1))+1;    %where to perform the mutation?



 153:         old=solpair(pos,1);



 154:         new=bincompl(old); %mutation call



 155:         if bin2dec(new)>=num_cit



 156:             new=old;    %if the complement exceedes the valid number for a city, don't change it



 157:         end



 158:         idx=strfind(solpair(:,1),cell2mat(new));



 159:         for k=1:size(solpair,1)



 160:             if cell2mat(idx(k))==1



 161:                 solpair(k,1)=old;



 162:                 break 



 163:             end



 164:         end



 165:         solpair(pos,1)=new;



 166:     end



 167:     if (maxmu-m1)~=0



 168:         for n=1:(maxmu-m1)



 169:             pos=round(rand*(size(solpair,1)-1))+1;    %where to perform the mutation?



 170:             old=solpair(pos,2);



 171:             new=bincompl(old); %mutation call



 172:             if bin2dec(new)>=num_cit



 173:                 new=old;    %if the complement exceedes the valid number for a city, don't change it



 174:             end



 175:             idx=strfind(solpair(:,2),cell2mat(new));



 176:             for k=1:size(solpair,1)



 177:                 if cell2mat(idx(k))==1



 178:                     solpair(k,2)=old;



 179:                     break 



 180:                 end



 181:             end



 182:             solpair(pos,2)=new;



 183:         end



 184:     end



 185:     mutsol=solpair;



 186: end



 187:  



 188: function bcomp=bincompl(binstring)



 189:     x=cell2mat(binstring);



 190:     y={};



 191:     for n=1:size(x,2)



 192:         y=strcat(y,{[num2str(xor(str2double(x(n)),1))]});



 193:     end



 194:     bcomp=y;



 195: end




p1ae