Doc Rivas' Blog

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));

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

    if strcmp(button,'Randomly')

        points=rand(num_cit,2)*100;

        dismat=zeros(num_cit);

        for r=1:num_cit

            for c=1:num_cit

                if c>r 

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

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

                end

            end 

        end        

    else

        %do manual

    end

    %imagesc(dismat);

    %initial parameters

    solsnum=256;     %number of total solutions

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

    elitism=1;      %best ranked solutions to keep

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

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

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

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

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

    tic

    %generate initial random solutions

    sols={};

    for n=1:solsnum

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

    end

    fitsols=0; it=1;

    %first iteration begins

    contcrit=1;

    while contcrit        

        for n=1:solsnum

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

        end

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

        history(it)=lowfit;

        contcrit=evalstopcrit(history,maxiwnch);

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

        if contcrit<0

            toc

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

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

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

            pause;  rsols(:,1)

            break;

        end

  

        figure(hfig);

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

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

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

  

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

        %offspring generation.  First evolve the best ranked

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

        %then generate new random solutions

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

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

        end        

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

        %reached  

        sols=nsols;

        it=it+1;

    end

end

end

  

function rsol=randombinsol(ncities,nbits)

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

    n=0;

    while n<ncities

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

        if ~any(dsol==cand)

            n=n+1;

            dsol(n,1)=cand;

        end

    end

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

end

  

function totdist=evalfitness(propsol,dismat)

    totdist=0;

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

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

    end

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

end

  

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

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

    lowfit=rsols(1);

    rsols={};

    for n=1:size(sols,2)

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

    end    

end

  

function cont=evalstopcrit(history,maxiwnch)

    cont=1;

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

        cont=0;

    elseif size(history,2)>=maxiwnch

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

        endpoint=size(history,2);

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

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

        if tthist==0

            cont=-1;

        end

    end

end

  

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

    t1evosol={}; t2evosol={}; evosol={};

    for n=1:2:total

        t1evosol=rsols(:,n);

        t2evosol=rsols(:,n+1);

        crossol=bincrossover(t1evosol, t2evosol, mco);

        mutsol=binmutation(crossol, mmu, num_cit);

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

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

    end

end

function crossol=bincrossover(sol1,sol2,minco)

    %randomly selecting the point of crossover based on the minimum

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

    solt=sol1;

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

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

    solt=sol2;

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

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

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

end

  

function mutsol=binmutation(solpair,maxmu, num_cit)

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

    for n=1:m1

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

        old=solpair(pos,1);

        new=bincompl(old); %mutation call

        if bin2dec(new)>=num_cit

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

        end

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

        for k=1:size(solpair,1)

            if cell2mat(idx(k))==1

                solpair(k,1)=old;

                break 

            end

        end

        solpair(pos,1)=new;

    end

    if (maxmu-m1)~=0

        for n=1:(maxmu-m1)

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

            old=solpair(pos,2);

            new=bincompl(old); %mutation call

            if bin2dec(new)>=num_cit

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

            end

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

            for k=1:size(solpair,1)

                if cell2mat(idx(k))==1

                    solpair(k,2)=old;

                    break 

                end

            end

            solpair(pos,2)=new;

        end

    end

    mutsol=solpair;

end

  

function bcomp=bincompl(binstring)

    x=cell2mat(binstring);

    y={};

    for n=1:size(x,2)

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

    end

    bcomp=y;

end

Technorati Tags: artificial intelligence,cnf formulas,machine learning,matlab code

Write a program to generate random CNF formulas. Your program should receive as parameters n, the number of variables, k, the number of literals per clause, and m, the number of clauses. Make sure your program does not generate clauses with repeated variables.

MATLAB CODE

        1: clear all; close all; clc

       2: n=input('Number of variables n=');

       3: k=input('Number of literals per clause k=');

       4: m=input('Number of clauses m=');

       5: if k>(2*n) 

       6:     errordlg('number of literals per clause must be less or equal to 2 times n');

       7: else

       8:     xn=zeros(1,k);

       9:     fprintf('\n\n');

    for o=1:m

        if o==1

            fprintf('  (');

        else

            fprintf('\n^ (');

        end

        for p=1:k

            xnt=floor(rand*n);

            while any(xn==xnt)

                xnt=round(rand*n);

            end

            xn(p)=xnt;            

            if p~=1 

                fprintf(' v ')

            end

            if round(rand)==0

                fprintf('!');

            end

            fprintf('x%i',xnt);

        end        

        fprintf(')')

    end

    fprintf('\n\n');

end