Stochastic Optimization Algorithm: Four Cases

Case 1: Traveling Salesman Problem

Answer 2.1 a)

The following is to illustrate how to compute the total distinct possible paths for each city :

• Suppose the total numbers of Cities = N Cities
• Total numbers of all possible paths of each city \(= (N-1)*(N-2)(N-3)*....*1 = (N-1)!\)
• Since for each city connected to other city path, two cities are symmetric and undirectly connected \(C_{hk} = C_{kh}\)
• Therefore,the total number of distinct paths of each city in TSP should:

\[\begin{equation*} \mathrm{SteptPath}_{distinct} = \frac{(N-1)*(N-2)(N-3)*....*1}{2} = \frac{(N-1)!}{2} \end{equation*}\]

Answer 2.1 b)

• The folder of “Problem21_GA21B” included as follows:

  • GA21b.m (This is the main file)

  • findLocalCityShortestPathLength.m

  • cartesianDistanceMeasure.m

  • computeShortestPathLength.m

  • TournamentSelect.m

  • Mutate.m

  • EvaluateIndividual.m

  • InsertBestIndividual.m

  • LoadCityLocations.m

  • InitializePopulation.m

  • InitializeConnections.m

  • InitializeTspPlot.m

  • PlotPath.m

  • BestResultFound.m (for Problem 2.1 b, c and e)

Best Path Length: GA

Best Path Sequence: GA

Answer 2.1 c)

• Please refer to folder of “Problem21_Q21C_Q21D” which contained all required m files

  • mainACO21c.m ( This is the main program to run AntSystem.m)

  • AntSystem.m (Restricted to not allow any modification of this file)

  • GetNearestNeighbourPathLength.m

  • GetVisibility.m

  • UpdatePheromoneLevels.m
    

  • ComputeDeltaPheromoneLevels.m

  • GeneratePath.m

  • GetPathLength.m

  • cartesianDistanceMeasure.m

  • InitializePheromoneLevels.m
    

  • InitializePopulation.m

  • InitializeConnections.m

  • InitializeTspPlot.m

  • LoadCityLocations.m
    

  • PlotPath.m

  • BestResultFound.m (for Problem 2.1 b, c and e)

  • NNPathLengthCalculator.m (for Problem 2.1 d)

  • GetNearestNeighbourPathLengthStartingCityYouEntered (for Problem 2.1 d)

Best Path Length: ACO

Best Path Sequence: ACO

Answer 2.1 d)

• The NNPathLengthCalculator.m should be run under the folder of “Problem21_Q21C_Q21D”
• Under this script you can enter your city ID number from 1 to 50
• The calculator will display the correponding Nearest Neighbour Path Length.

Answer 2.1 e)

• Please refer to BestResultFound.m under the folder of “Problem21_Q21C_Q21D”

• With Ant colony optimization (ACO) Algorithm, the shortest path length found to be approximately 122 .

• With GA Algorithm, the shortest path length found to be 151.

• With NNPathLengthCalculator, the shortest path length is between 122 to 160.

• The poor computional performance with GA Algorithm in TSP can be explained as follows:

  • First reason is that GA Algorithm initializes with a random path in TSA, which is hard to guarantee a short initial path. With the initial longest path , it requires more swapped-steps to reach the nearest neighbour step path length.

  • Second reason is the general GA Algorithm can easy get stuck at a local minimum point (attractor) and hard to ganurantee a global mininum (or the shortest of neighbour step path length). The problem can not solved by regulating the parameters of selection scheme, crossover probability and mutation probability.

• Hence, the best performance to solve TSA problem is to use ACO Algorithm.

Case 2: Particle Swarming Problem

\[\begin{equation*} f(x,y) = (x^{2}+y-11)^{2} + (x+y^{2}-7)^{2}; \quad (x,y)\in [-5,5 ] \end{equation*}\]

• Please refer to folder of “Problem22” which contained all required m files

  • mainPSO22Runs.m (main program : repeatly run “PSO22.m” to obtain all four local minima )
  • PSO22.m (This file is to obtain one local minimum per single run)
  • positionPSOUpdate.m
  • velocityPSOUpdate.m

• The following figure and table are to show the local minima obtained by the Particle Swarm Optimization (PSO) Algorithm for the TSP.

Four Cases Outputs

Conclusions:

• Empirical trials found that it is possible to obtain all four local minima by repeatly running “PSO22.m” in a range of 8 times to 20 times.

• Please notes: All results are subjected to parameters chosen.

Case 3: Optimal Braking Systems Problem

Case 4: Function fitting using LGP

• The data series is generated with the following function form :

\[\begin{equation*} g(x) = \dfrac{a_{0}+a_{1}x +a_{2}x^{2}+...+a_{p}x^{p}}{b_{0}+b_{1}x +b_{2}x^{2}+...+b_{q}x^{q}} \end{equation*}\]

• The corrsponding error computaion is :

\[\begin{equation*} E_{rms} = \sqrt{\dfrac{1}{K}\sum_{K=1}^{K}(\hat{y}_{k}-y_{k})^{2}} \end{equation*}\]

• Number of data points = \(K\)

• Fitness Value:

\[\begin{equation*} f=\dfrac{1}{E_{rms}} \end{equation*}\]

\[\begin{equation*} \begin{cases} b_{1} =-4.7967 \\ b_{2} =+4.7967 \\ b_{3} =-4.7967 \\ b_{4} =-4.7967\\ b_{5} =+4.7967 \\ b_{6} =-4.7967\\ E_{rms} =2.3871\mathrm{x}10^{-6} \\ \end{cases} \end{equation*}\]

\[\begin{equation*} g(x) = \frac{ b_{1}x^{3}+ b_{2}x^{2} + b_{3}}{b_{4}x^{4} +b_{5}x^{2} +b_{6}} \end{equation*}\]

\[\begin{equation*} =>g(x) =\frac{ x^{3} - x^{2} +1 }{ x^{4} - x^{2} + 1} \end{equation*}\]

Curve-fitting for given datasets with GA operators

• TestFit.m

• An Example of g(x) for testing :

\[\begin{equation*} g(x) = \dfrac{1+ 2x +3x^{2}+4x^{4}}{1+3x +5x^{2}+7x^{3}+9x^{4} +11x^{5}} \end{equation*}\]

Curve-fitting for given datasets with GA operators: Output01

Curve-fitting for given datasets with GA operators: Output02

Curve-fitting for given datasets with GA operators : Output03

Curve-fitting for given datasets with GA operators : Output04

TestLGPChromosome.m

TestLGPChromosome.m

• The following figure is to verify the best chromosoms obtained from the main program and decode back to equation function.

Result verified with TestLGPChromosome.m

Conclusion

• The following optimal curving-fitting equation estimated with GA operators; and its computational output is apprendixed for reference.

\[\begin{equation*} G(x) =\frac{ x^{3} - x^{2} +1 }{ x^{4} - x^{2} + 1} \end{equation*}\]

Appendix

Computational Output04