Home

ADEP User Manual ADEP 1.0 User Manual Compiled

1. Initialization Update Global Solution Update Tabu List 4 X Population Evaluation Stopping Condition oOo Y End Navigate Neighborhood Perform Move Figure 5 7 Diagram Panel showing work flow of Tabu Search algorithm figure 5 7 shows the work flow of Tabu Search Algorithm in the Diagram Panel when Tabu Search with Integer Permutation representation and C language are selected in the Algorithm Configuration Dialog We will explain what has happened in each of the functional blocks 1 Initialization In this functional block a population of individual solutions are randomly generated integer permutation in additional for each of those solution a tabu list is created 2 Population Evaluation In this functional block an objective value is calculated and assigned to each individual solution in the population 109 Stopping Condition this functional block determine the Simulated Annealing al gorithm should terminate and terminate the algorithm when certain termination conditions are fullfilled notice it is in a while loop which we have called a gener ation refer to Section 4 2 1 In this functional block the global best solution Sbest 18 also updated if its fitness is found to be less than one of the individual solution in the population Navigate Neigborhood in this functional block for each solution s in the popula tion a disturbance mechanism gener
2. n Listing 3 11 Code Listing for Problem lt T gt delcaration in Problem h file with the virtual method record _individual added Let us study the Problem lt T gt record_individual as listed in B 11 the method is passed to parameters individual and filename the parameter indivuidal the the global best solution passed to the individual by the ADEP algorithm while the parameter file name is the filename generated by the ADEP algorithm which the user can optionally use to save the information of global best solution individual in the current algorithm generation of course the user can use his invented file name for the file to which to save the solution Now suppose that we use the filename generated by the ADEP algorithm and 60 implement the Problem lt T gt record_individual as shown in Code Listing virtual void record_ individual Individual lt I gt amp individual std string filename std ofstream outfile outfile open filename c_str outfile lt lt Current_ Generation _ lt lt this gt getCurrent Generation lt lt as outfile lt lt Solution Objective _ Value _ lt lt individual m_ fitness 0 lt lt n outfile lt lt a PAIA LA LTT LT 0 Chromosome lt I gt amp solution individual 0 int N solution size for int i 0 i lt N i outfile lt lt Queen_ lt lt i lt lt _ row lt lt i lt lt col lt lt solution i lt
3. lt parameters gt _section_of_the_ lt lt filename lt lt n return false return true 128 41 Listing 8 3 modified Problem lt T gt readInput in Code listing reader getParam Value csv found looks for lt param gt el ement with name csv in the lt parameters gt section of the problem xml file if the lt param gt element is found found is set to value the value attribute of the lt param gt element is returned As seen in the modified problem xml listed in 8 1 the value attribute of the lt param gt element is the relative file path to the samples2 csv file m_ samples LoadFile csv_file_ name loads the content of the samples2 csv file into m_ samples 8 3 7 Modify Problem lt T gt _ evaluate As discussed in section 8 3 2 There introduces two decoding method to obtain the parameters 3 and i In the Problem lt T gt _ evaluate the Method 2 is used for decoding in the modified problem xml it is defined that the chromosome length is 100 this is divided into 2 equal chromosome section of length 50 the decimal point is placed after the 9th bit from the left of the chromosome section the first bit of each chromosome section is used for signed bit Therefore both B has a range between 512 to 512 The modified source codes for Problem lt T gt _ evaluate is shown in the code listing virtual double _ evaluate Individual lt I gt amp individual double objective value 0 0 C
4. lt solution gt lt gene index 0 value 5 gt lt gene index 1 value 3 gt 54 46 AT 48 49 50 51 52 53 54 59 56 57 58 59 lt gene index 2 value 0 gt lt gene index 3 value 4 gt lt gene index 4 value 7 gt lt gene index 5 value 1 gt lt gene index 6 value 6 gt lt gene index 7 value 2 gt lt solution gt lt problem date Thu_Jun_12_12 33 08 _2008 amp x0A chromosome _length 8 best_known__solution 28 000000 best_known_ solution __exist true search_max true gt lt simulation gt lt output gt Listing 3 8 Code Listing for results xml after running of adep exe two times 3 5 2 Obtain Solution by overriding Problem_Base lt T gt interpret in the Problem lt T gt class For some user who is looking for customized output from ADEP generated algorithm for example so that the output can be read and displayed by a GUI results xml might not be suitable This may be because the user is responsible for the algorithm design while another developer is working on the GUI and they have already agreed on the format of the solution to be passed to the GUI developer or because the user is not familiar with XML parsing which is required if the user is going to develop an GUI to read the results xml file In this case ADEP generated algorithm does provide a way for the user to create their customize output This is to override the Problem_ Base lt T gt i
5. referred to Section 3 5 4 will not be called 87 ii Record Solution in XML is set to Enabled indicating that the results xml will be generated referred to Section 3 5 1 4 Offspring Producer a Fitness Scaling is set to No Scaling indicating that the fitness of the indi vidual solutions will not be scaled before the Selection of individuals into mating pool is started b Parent Selection i Parent selection method is set to Random indicating the individual solu tions are randomly picked from the current population into the mating pool ii Mating Pool Size is set to Low selected_parent_count 2 indicating that only 2 individual solutions are selected from the current population into the mating pool c Cross Over i Cross Over Method is set to Two Point ii Cross Over Rate is set to High crossover_rate 1 0 indicating that Two Point Crossover will be applied to all pairs of individual solutions in the mating pool to generate children for the offspring population if it is less than 1 then some pairs of individual solution in the mating will be copied directly into the offspring population 5 Offspring Mutation a Mutation Method is set to k Swap b Mutation Rate is set to High mutation_rate 0 01 indicating that each individual solution in the offspring population will have 1 chance of mu tation 6 Offspring Local Search a Offspring Local Search Method is set to Disabled indicating that no
6. 1 Chart exe Chart exe intermediate manifest this is the Fitness VS Generation Chart application 2 StatisticsInfo exe results htm this is the StatisticInfo application 3 cmd bat this is the batch file written to invoke Chart exe and StatisticsInfo exe applications at the end of the algorithm test run 4 algorithm information xml this is a generated XML file that describes the al gorithm s representation and programming language used 5 benchmarks a folder that contains all the Benchmark files created for the Ex NQueensProblem project Among those items algorithm _information xml and benchmarks folder are not in volved with any processing they are merely there as information and can be removed without affecting the algorithm running The Fitness VS Generation Chart ap plication cmd bat as well as the StatisticInfo application forms the performance measurement reporting subsystem that is invoke at the time the algorithm is about to exit Now in the folder C2 double click the adep exe to run it An interesting observa tion will appear as shown by figure 4 11 just before adep exe terminates the Fitness VS Generation Chart and the StatisticInfo application are automatically invoked and both applications showed the statistics information of two simulations instead of a single simulation How can this be possible This is because both Fitness VS Gen eration Chart and StatisticInfo are capable of re
7. 4 Description This describes the function of the operator or parameter and how it can be appropriately used Notice there are two command below the Node Information Panel that read Up date and Description the purpose of the Update command is to update the status of the operator node currently activated in the Functional Block Panel and how to use it is to be discussed in Section 4 2 5 The purpose of the Description command is to display the code hint for the activated operator node in the Functional Block Panel but it offers additional information other than those displayed in the Code Hint of the Node Information Panel Now with the operator node Random selected in the Functional Block Panel click on the Description command A Operator Node Description dialog pop up as shown in figure 4 16 The three tabs in the Operator Node Description dialog are described below 1 Operator Description This is the same as the Description element in the Code Hint of the Node Information Panel Due to the size of the Node Information Panel longer description may not display fully in the Panel but the Operator Description can show the full length description of the operator node 2 Operator Detail This tab displays the other 3 elements available in the code hint of the Node Information Panel Furthermore it also displays the C source codes file will be transferred from ADEP into the root_ folder selected by the user when activatin
8. lt gen generation 37 fitness 27 000000 time 16 000000 gt lt gen generation 184 fitness 28 000000 time 78 000000 gt lt generations gt 51 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 lt solution gt lt gene index 0 value 4 gt lt gene index 1 value 1 gt lt gene index 2 value 3 gt lt gene index 3 value 6 gt lt gene index 4 value 2 gt lt gene index 5 value 7 gt lt gene index 6 value 5 gt lt gene index 7 value 0 gt lt solution gt lt problem date Thu_ Jun _12_11 58 01_2008 amp x0A chromosome _length 8 best_known_ solution 28 000000 best_ known_ solution _exist true search _max true i gt lt simulation gt lt output gt Listing 3 7 Code Listing for results xml as produced by the running of adep exe on 8 Queens Problem Let us analyze the lt simulation gt section of the XML code above the lt simulation gt section contains 3 sub sections lt generations gt lt solution gt lt problem gt 1 The lt generations gt section include information about the fitness change at dif ferent generation for user confused about what is a generation refer to section 4 2 1 for a short tutorial on Hybrid GA only the generation at which the fitness change will be recorded in this section lt generations gt contains one more more lt gen gt elements each lt gen gt elements record the gene
9. selected true gt lt LVRP_node name high type variance selected true gt lt param gt lt param_name gt crossover_rate lt param_name gt parai pE OUD TE Spar yE lt param_value gt 1 0 lt param_value gt lt param gt lt LVRP_node gt lt LVRP_node name Jow type variance selected false gt lt param gt lt param_name gt crossover_rate lt param_name gt lt param_type gt doub1e lt param_type gt lt param_value gt 0 1 lt param_value gt Figure 4 28 myConfig adep file opened in notepad 99 Chapter 5 Working With Various Algorithms So far we have been working with the Hybrid GA with integer permutation represen tation on the N Queens Problem But ADEP is not merely application that generate Hybrid GA using integer permutation Currently ADEP supports Hybrid GA using integer permutation representation binary string representation and floating point value representation Apart from the Hybrid GA ADEP also support code gener ations of other popular meta heuristic algorithms that include Simulated Annealing Tabu Search Ant Colony Optimization Multiple Random Restart Adaptive Search This chapter you will learn 1 How to switch between different algorithm representation and language within ADEP 2 Brief description of Hybrid GA with different representations 3 Brief description of other meta heuristic algorithms 5 1 Howto Switch Between Different Algorithms Rep resentations and Language
10. the current configuration fail to find the optimal solution Next Let us look at the StatisticInfo table as shown in figure 4 10 The recorded statistics in the table are explained below 1 Simulation Run at the time at which the test running is started 2 Number of Simulation total number simulations or test runs recorded both Fit ness VS Generations and StatisticInfo can record multiple test runs Which will be further explained later 3 avg CPU time ms Dest where CPU _ time s is the CPU time spent for the simulation s and N is the total number of simulations 4 min CPU time ms min CPU _time s s 1 N s N 2 i tial _generahon s ere total_ generation s the number of 5 avg Generations generations spent in simulation s before the algorithm finds the final global best solution 6 min Generations min total_generation s s 1 N 75 Chart Fitness VS Generation 103 6 206 2 308 8 411 4 514 0 616 6 719 2 821 8 924 4 1027 Fitness YS Generation Figure 4 9 The Fitness VS Generation chart obtained by test runing the hybrid GA on 100 Queens Problem 76 StatisticsInfo Simulation Run at Thu Jun 12 18 08 03 2008 Number of Simulation avg CPU time ms min CPU time ms avg Generations min Generations avg Fitness 4920 000 best Fitness 4920 000 best known solution 4950 000 avg Gap 0 606 min Gap 0 606 Figure 4 10 StatisticInfo table obtain
11. 1 2 1 What Are Real life Combinatorial and Numerical Optimization Lathe ne eay aed eee CR GEG a wees ae 8 oo 1 2 2 What Are Meta heuristic Algorithms 1 2 3 ADEP Allow Users To Design and Implement Complex and Ef ective Meta heuristic Algorithms 9 1 2 4 ADEP Allow Users To Configure An Algorithms Performance e abe gs pee dees 10 rere 11 1 3 What Features Does ADEP Have aoaaa aaa a 12 1 3 1 Intuitive GUI aaa a 12 1 3 2 Automatic Generation of Source Codes a aa aa aaa 13 1 3 3 Highly extensible algorithm framework 13 1 3 4 ADEP Has Built in C Compilers 14 1 3 5 ADEP Has Built in Java Compiler 15 1 3 6 ADEP allow configured algorithm to test run in the ADEP 15 1 3 7 ADEP can replace the task of looking for the best configured a 16 1 3 8 Other Features of ADEP oe a eee Ree ee ee 8 17 1 4 Why Choose ADEPT oee Hae hea ee Ee oe eS ae dS ee es 17 19 2 1 Launch ADEP Installer 2 0 a a 19 2 2 Enter ADEP Installer Password 19 GO dope seo dog hed tesa ar ned fe eee 22 ee ee ee ee ae 24 3 Generate and Compile ADEP Source Codes 27 3 1 How to Use ADEP to Generate C Source Codes 27 3 1 1 Explain ADEP GUI oe 6 4a hae wae oie oe hee ea eS 28 3 1 2 Generate Source Codes 2 a a a a a 30 3 2 What are the C source codes generated o aon a a a aaa 31 a a 34 3 3 1
12. 58 Q oF W NS FR lo Figure 3 12 The table printed by output htm file generated by Prob lem lt T gt interpret since it is called only once at the exit of the program to output the final solution What the user should do is to override the Problem_ Base lt T gt record_individual method in the Problem lt T gt class record_individual is the method called by the ADEP algorithm whenever the global best solution has changed Therefore by implementing this method the user can save the global best solution whenever that solution has changed To override Problem_ Base lt T gt record_individual method in the Problem lt T gt class copy and paste the Problem_ Base lt T gt record_individual method into the Problem lt T gt class declaration in the Problem h file 3 11 shows the code listing of the Problem lt T gt class declaration with comments and implementation codes omitted after the Problem_ Base lt T gt record_individual has been added to Problem h file namespace ADEP template lt class T gt class Problem public Problem_Base lt T gt public 59 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 virtual bool readInput const char filename virtual double _ evaluate Individual lt I gt amp individual virtual void interpret Individual lt I gt amp individual virtual void record_ individual Individual lt I gt amp individual std string filename
13. 7 select the Ex NQueensProblem from the Problem drop down list and then select the 100QueensBenchmark from the Benchmark drop down list 71 Create TestBench ogram Files ADEP Run Available Testbench Cpp_Integer_QAP Benchmarks 100QueensBenchmark b Create Benchmark Cpp_Integer_TSP Cpp_Integer_URAV Java_ACO_URAV Java_Binary_LinearLeas Java_Binary_MinimumP Java_Continuous_Linear Java_Integer_CVYRP Java_Integer_NQueen Java_Integer_ QAP Update Benchmark Delete Benchmark TestBench Directory Add File lt gt problem Problem h Open Problem Folder Rename Problem Delete File Delete Problem The TestBench lt Ex_NQueensProblem gt is based on the cpp version of an algorithm in Integer Permutation representation Figure 4 6 TestBench Manager with the Ex NQueenProblem selected in the list box 72 Problem Benchmark Details Folder Compilers Ex_NQueensProblem 100QueensBenchmark benchmark FA problem Ex_NQueensProblem overview chromosome_length value attribute 100 best_known_solution existed attribute true value attribute 4950 000000 maximization value attribute true Borland C 5 5 CI Show Command Window During Compilation Browse Figure 4 7 The Run dialog with Ex NQueensProblem and 100QueensBench marks selected 73 Next in the Run dialog shown in figur
14. Gap 60 606 min Gap 240 606 a internet Figure 4 11 Screen shots at the end of the program execution of adep exe when run from folder C2 The other question that some of the users might want to ask is what modifica tion is done in the source codes by ADEP such that the compiled adep exe is able to invoke the Fitness VS Generation Chart and StatisticInfo just before adep exe terminates This is actually quite easily done ADEP simply open the main cpp file located in root_ folder main folder and add a line system cmd bat before the re turn 0 statement in the main function So just before adep exe terminate it invokes the cmd bat batch file which then invokes Fitness VS Generation and StatisticInfo which then reads data from results xml and display the statistics accordingly 79 algorithms benchmarks console csv doc elements O functors global_solution_records io main fom operators problem 3 tinyxml utilities adep dsp Pladep exe adep sin aladep veproj algorithm_information xml Chart exe Chart exe intermediate manifest jema bat E compile bat makefile problem xml results htm results xml StatisticsInfo exe E adep dsw Figure 4 12 The files and folders in the root_ folder C2 generated by the ADEP test run procedure 4 2 How to Configure an Algorithm to Improve its Performance In sectionj4 1 3 the Fitness VS Generation chart obtai
15. Size operator node oaoa aa 92 19 Operator Node Configuration dialog with the parameter population _ size Sererre rT rer rere cere ere 92 20 operator tree of Population Initialization after the update of Medium a 93 21 population _size is shown to change to 60 after the operator node update 93 22 Fitness VS Generation Chart display for the 100 Queens test run after Dee sd peek eee eee oeseee oes 94 4 23 Statistics Info table display for the 100 Queens test run after the Oe PA ee Be oe eee Se ee ee ee ey 95 4 24 Fitness VS Generation chart for test running 100 Queens after the ee ee ee ee 96 Sh hae ek Bik ee Bec a eee ease 96 after selecting Two Genes Swap DFT 2 2 ee 97 ee ee eee ee ee 97 4 28 myConfig adep file opened in notepad 99 5 1 Algorithm Selection dialog pop up after click the button in the Algo Se ete e Chee eke eee eee ee eee eee 101 5 2 ion 102 ETET 102 5 4 Fitness VS Generation and StatisticInfo Application invoked at the wir 104 ee eee ee ee ee ee ee ee ee ee 106 5 6 Work flow of Simulated Annealing algorithm in the Diagram Panel 107 Diagram Panell 24064 Se geek op ewe Ae OA Re od Pe AS eee 111 5 9 work flow of Simple Random Search displayed in the Diagram Panel 114 8 1 a Simple Linear Regression Model 119 8 2 Algorithm Selection dialog configuration to generate codes for solving si
16. and display in the studio editor windows as shown in figure For user that use VC 2005 similar steps can be taken to load the Problem h file into the editor panel If you do not have any of those IDEs you can still access and modify the Problem h file by navigating to the folder problem in root_ folder C1 and open the Problem h file in the folder using your favorite editor Figure 3 10 shows the Problem h file opened in notepad ADEP source code files usually contains extensive comments to explain the various features in the source codes Problem h is no exception Ignore those comments Prob lem h essentially contains the definition of the class Problem lt T gt under the namespace ADEP In the Problem lt T gt declaration apart from the constructor and destructor method which the user does not need to pay attention during most implementations 40 adep Microsoft Visual C C C1 problem Problem h DER Eie Edit view Insert project Buid Tools Window Help la SO laeo o DB Balorpetement z ta Probiem lt ciass T gt zjin class members Problem ERS lt li _evaluate Individual lt T gt amp individual this is where the objective function for the problem is defined 7 y fff lt 40 gt Workspace adep 1 project s the user can start their own implementation at after the comment lines which start with the words TODO E adep files template lt class T gt a ng class Problem public Pro
17. assignment problem only the cost function is expressed in terms of quadratic inequalities hence the name 116 Chapter 7 ADEP Example Traveling Salesman Problem 117 Chapter 8 ADEP Example Regression Analysis In this chapter you will learn 1 What is Regression Analysis 2 How to solve a regression analysis problem 3 How to represent the parameters solution as binary string in binary GA 4 How to represent the parameters solution as floating point string in Continuous GA 5 How to define objective function for regression analysis 6 How to use ADEP to generate and modify codes to solve regression problem 8 1 What is Regression Analysis 8 1 1 Regression Explained Regression analysis is a technique used for the modeling and analysis of numerical data consisting of values of a dependent variable response variable and of one or more in dependent variables explanatory variables The dependent variable in the regression equation is modeled as a function of the independent variables corresponding parame ters constants and an error term The error term is treated as a random variable 118 It represents unexplained variation in the dependent variable The parameters are es timated so as to give a best fit of the data Most commonly the best fit is evaluated by using the least squares method but other criteria have also been used Regression can be used for prediction including forecasting of time
18. developed to look for solution with good enough quality and find those solutions within short period of time however those heuristics usually suffered from the tendency of being trapped in the local optimima and their performance become highly unreliable As a results in recent years many highly effective meta heuristic algorithms were developed that incorporate mechanism to help the algorithm to escape from local optimia this branch of algo rithms include evolutionary algorithms simulated annealing tabu search ant colony optimization and neural networks have surfaced as viable stochastic optimization tech niques 1 2 3 ADEP Allow Users To Design and Implement Complex and Effective Meta heuristic Algorithms With these basic understanding of real life optimization problems and meta heuristic algorithms let s examine what needs does ADEP fullfill The state of the art research on meta heuristic algorithms has made significant ad vancement in the last two decades This coupled with the technological advancement in computational horsepower have opened up avenues to explore problems of complexity level that were previously considered insurmountable In this regards rapid design and development of meta heuristic algorithms has become an important and challenging issue The current meta heuristic algorithm development methodology usually requires significant effort in codes generation and modifications As a result the quality of the meta h
19. features available in ADEP as discussed in are not available in other meta heurist PSE or software package currently available This makes ADEP stands out from those other software packages 18 Chapter 2 Installing ADEP This chapter you will learn 1 How to set up ADEP in your computer 2 How to register your copy of ADEP 2 1 Launch ADEP Installer The ADEP setup file is available as a Windows installer To install ADEP in your computer launch the ADEP Windows installer The following figure is the screen shot of the installer program after it is launched Click Next to proceed 2 2 Enter ADEP Installer Password The figure shows the next screen of the installer that appear Figure 2 2 asks the user to enter the ADEP installer password the default password is adep or it might be specified otherwise by the software distributor from whom the user can obtain the installer password Enter the installer password then press Next 19 fe Setup ADEP Welcome to the ADEP Setup Wizard This will install ADEP 1 0 on your computer It is recommended that you close all other applications before contir Wit 1g Click Next to continue or Cancel to exit Setup Figure 2 1 ADEP Installer Screen Shot After Launch 20 18 Setup ADEP Figure 2 2 Enter installer password 21 i6 Setup ADEP Select Destination Location Where should ADEP be installed Setup will install ADEP into the following f
20. figure lt xml version 1 0 gt lt problem name Simple_Least_ Squares gt lt overview gt lt chromosome_length value 100 gt lt best_known_ solution existed false value 0 gt lt maximization value false gt lt overview gt lt parameters gt lt param name csv value data samples2 csv type string gt 125 EJ Microsoft Excel samples2 csv Figure 8 3 samples2 csv 12 lt parameters gt 13 14 lt problem gt Listing 8 1 The problem xml for the Simple Least Squares problem 8 3 6 Modify Problem lt T gt readInput method in Problem h Open the Problem h file in the root_ folder problem folder add the include statement Hinclude csv_doc CSVDoubleDocument h below the other include statements at the top of the Problem h file CSVDoubleDocument h file contains definition for CSVDoubleDocument class the object of this class is able to read csv file which contains only floating point values Add a member variable m_ samples of class CSVDoubleDocument to Problem lt T gt below the comment line TODO define the data structure for the problem here in the Problem h file as shown below 126 Oo Ont nm oF W DH ee a aoa a O O AN OT FP WY KF O CO NO Oo BW DO FR include include csv_doc CSVDoubleDocument h namespace ADEP template lt class T gt class Problem public Problem Base lt T gt public virtual bool readInput const char filename TODO
21. is minimized w in equation is used to estimate the values of the unknown pa rameters are inversely proportional to the variances at each combination of dependent variable y 1 o2 8 3 Wi X There are a number of ways to estimate w in equation interested readers can refer to literatures on feasible Weighted Least Squares or iterated 2 steps Weighted Least Squares methods 8 3 Simple Linear Regression using ADEP Generated algorithm with Binary Solution Representation In this section we will show how solve simple linear regression using ADEP generated algorithm with binary solution representation the algorithm that we would be using is the Hybrid GA with code generated in C 121 8 3 1 Represent Simple Least Squares Solution using Binary String The solution of the simple least squares regression is the values Bo and By in y Bot fix that best fit the samples x y in table 5 1 We need to find a decoding method to translate a binary string into the floating point values of Bo and Bi There are several ways to do this But first of all we need to know roughly the upper bound and lower bound of both parameters let Bases and Dieu be the upper and lower bounds for 4 and Bimar and Birin be the upper and lower bounds for Bi assume that we have a binary string chromosome of length 2l we divide the chro mosome into two section of equal length Each section will then represent the value of Bi i 0 1 For each of tho
22. of the same class Hence it is common to mix and match between metaheuristics or at least one metaheuristic and one local search technique It has also become a norm in algorithms development to mix and match between the various available techniques to develop algorithms that are able to capitalize on the strengths and merits of the various techniques This has also given rise to a group of algorithms known as memetic algorithm To configure a meta heuristic algorithm to improve its performance on a problem it usually involves tremendous amount of time in inventing new algorithm operators as well as testing the those operators by embedding them back in the algorithm The process of configuring such hybrid algorithms can be made easier if there is a com putational platform to facilitate the algorithm design process Thus ADEP comes in handily in helping the users to design and configure highly efficient algorithm on a problem by making numerous configuration options available so that the user does not need to reinvent the wheels and focus on the high level of designing and configuring the algorithm ADEP makes the algoritm configuration process a much easier task by making the following features available 1 prev written modules and algorithm operators that the user can easily add or remove from the algorithm in designed by a few click of mouse 2 different parameters tunable in the algorithm can be fine tuned through ADEP GUI 3 built
23. parameter that individual is passed into the _ evalate this parameter is an Individual lt T gt object which represents a solution generated by Hybrid GA The purpose of _ evaluate is to calculate an objective value of the parameter individual and return the calculated objective value Earlier on in section and we have already written the pseudo code for the objective function of 8 Queens The first thing that we need to clarify is that in the code listing 3 3 3 what is representing the integer permutation x in the equatior3 1 To answer this question let us start to analyze the code below the comment action 1 in this code a local reference chromosome is created that is referenced to the first Chromosome lt T gt object stored in individual this reference chromosome refer to the actual integer permutatin x that we are interested in In the source code design of ADEP ADEP algorithms have an Individual lt T gt object as a single solution each Individual lt T gt object may keep one or more copies of Chromosome lt T gt objects The reason that ADEP algorithms have the solution representation data structure in this way is because for some algorithms there might be chances that a solution cannot be represented by a single Chromosome lt T gt object but need to be kept in multiple Chromosome lt T gt objects To ensure that such a case can be taken into account the Indiwidual lt T gt Chromosome lt T gt data structure is used so that an
24. saws OA rae n n e y 78 EE 80 4 2 1 Basic concept of Hybrid Genetic Algorithm 81 a 83 4 2 3 Understand the default configuration of Hybrid GA 86 4 2 4 Use ADEP Statistics panel to view the currently selected op TOTTE 39 4 2 5 How to Configure ADEP algorithm using the GUI 89 4 2 6 How to Save a Configuration 2 98 5 Working With Various Algorithms 100 5 1 How to Switch Between Different Algorithms Representations and Lan guages within ADEP 24 4 4 4 44 25444 254 eRe be See eG 100 5 1 1 Select Simulated Annealing algorithm 100 5 1 2 Generate and Modify Simulated Annealing Algorithm Source Codes to solve N Queens Problem 103 5 1 3 Test Run Simulated Annealing algorithm on the 100 Queens frat avg gy a aan e Gap eee Gt ea se we es 103 5 1 4 Configure Simulated Annealing Algorithm through ADEP GUI 105 eters 105 107 5 3 1 Simulated Annealing 2 22020 107 5 32 Tabi Search se S a8 0 amp Bee a ae i Be bre Bb Yew Ee 109 5 3 3 Ant Colony Optimization 24 111 5 3 4 Simple Random Search 4644546524684 ee ae ew ee 114 116 117 118 8 1 What is Regression Analysis o oo aaa a 020000008 118 8 1 1 Regression Explained ooa aaa 118 paa E ei aR Ae a ee ace 119 eea E a vk a G 120 8 2 1 Least Squares Method 20 120 eae eek BR Ure e amp oe 121 oye oe eee 121 5 1 Re
25. selects individual solutions from both the current population and the offspring population form the next generation population it 82 can be seen from figure 4 13 then the next functional block that will be run is Stopping Condition and hence the generation loop is form 4 2 2 Understand the symbols used in the Functional Block Panel and Code Hint available in Node Information Panel figure shows the operator trees displayed in the Functional Block Panel when the Population Initialization functional block is selected E E Population Initialization E a Initialization Method Pl Load z Random E a Population Size F high J low medium Figure 4 14 Operator Tree of the Population Initialization functional block In figure 4 14 the tree node that has a sign next to its caption is the operator currently selected to be used in the algorithm the operator tree in figure 4 14 indicates that the initialization method is Random and the population size is low What some observant users will discover now is that in figure 4 14 the operator node with a black icon is the one that is can is alway selected to be used in the configured algorithm this is termed property whereas the operator node that has an blue icon next to it is one that can be selected or deselected this is termed variance Therefore the selection of operator node Initialization method with black icon is compulsory In a GA one defi
26. series data inference hypothesis testing and modeling of causal relationships 8 1 2 Linear Regression Explained In linear regression the model specification is that the dependent variable y is a linear combination of the parameters but need not be linear in the independent variables For example in simple linear regression for modeling N data points there is one inde pendent variable x and two parameters J and 3 y Bo Bia straight line as shown in figure 4 Datapoints Regression 0 2 0 4 0 6 0 8 1 Figure 8 1 a Simple Linear Regression Model 119 In multiple linear regression there are several independent variables or functions of independent variables an example can be y Bo Pra Box 33 cos x2 84 tan z1 This is still linear regression as although the expression on the right hand side is non linear in the independent variable x and z it is still linear in parameters 6o 1 b2 83 and 4 8 2 A Simple Linear Regression Example Given below is the table of data points sampled from a system T y 10 2 569 20 2 319 31 2 058 40 1 911 50 1 598 100 0 584 Table 8 1 Data Sample from a System Assume the system can be modelled by y Bo 6 2 6 where e is an error term and the subscript 7 indexes a particular observation our objective is to find values Bo and i in a linear regression y Bo Brxi such that the linear regression best fit
27. simulation gt section will appear in the results xml file the code listing shows the contents of results xml after the adep exe was run two times lt xml version 1 0 gt lt output simulation _count 2 gt lt simulation index 1 gt lt generations gt lt gen generation 1 fitness 26 000000 time 0 000000 gt lt gen generation 37 Oo Ont anA wn Fe eR Oo e fitness 27 000000 time 16 000000 gt lt gen generation 184 fitness 28 000000 53 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 time 78 000000 gt lt generations gt lt solution gt lt gene index 0 value 4 gt lt gene index 1 value 1 gt lt gene index 2 value 3 gt lt gene index 3 value 6 gt lt gene index 4 value 2 gt lt gene index 5 value 7 gt lt gene index 6 value 5 gt lt gene index 7 value 0 gt lt solution gt lt problem date Thu_Jun_12_11 58 01 _2008 amp x0A chromosome _length 8 best_known _solution 28 000000 best_known_ solution __exist true search_max true gt lt simulation gt lt simulation index 2 gt lt generations gt lt gen generation 1 fitness 26 000000 time 0 000000 gt lt gen generation 4 fitness 27 000000 time 0 000000 gt lt gen generation 22 fitness 28 000000 time 15 000000 gt lt generations gt
28. the default Hybrid GA does not use it Basically this functional block applies local search to the individual solution generated by Population Initialization Stopping Condition this functional block determine the Hybrid GA should ter minate and terminate the algorithm when certain termination conditions are fullfilled notice it is in a while loop usually in the terminology of GA one single loop of this while loop is considered to be one generation as the popula tion go through reproduction selection crossover mutation local search survival selection and so on to generate a new population in one generation Offspring Producer this functional blocks select some individuals from the cur rent population into a mating pool using some selection methods based on the fitness of the individual solution and a offspring population of individual solu tions is generated from the mating pool by performing crossover between individ ual solutions in the mating pool Offspring Mutation this functional blocks try to mutate some of the individual solutions in the offspring population Offspring Evaluation this functional blocks calculate and assign a fitness value for each individual solution in the offspring population Offspring Local Search this is also optional the default Hybrid GA does not use it basically it performs lo cal search on certain individual solutions of the offspring population Population Updating this functional block
29. want to get back the default configuration he has to close the ADEP application and then reopen it This is quite inconvenient especially when the user has already found an good configuration but want to try some other configurations ADEP solve this problem by providing feature to save the user configured settings into adep file which can be loaded back into ADEP by double clicking the file or select ADEP menu File Open To save the current algorithm configuration settings to the adep file select ADEP menu File Save or File Save As The intereting feature is that adep automatically save configuration settings in all the algorithm framework available in ADEP including the different representation as well as language so if you configure an algorithm in integer permutation repre sentation and another algorithm in binary representation selection of representation will be discussed later chapters both of these two algorithm settings will be saved automatically the adep file is written in XML format and so is human reader to open the file in applications other than ADEP to view its content right click the file and select Open With popup menu figure shows the myConfig adep file open in notepad 98 k xml version 1 0 gt lt project name ADEP version 1 0 0 0 gt lt algorithm id HGA selected true gt lt display_name gt Hybrid GA lt display_name gt lt xm1l_folder_name gt Al1goLib HGA lt xml_folder_name gt lt s
30. you might want to change the active configuration to Release mode 2 If you have neither of this tool but has ADEP setup in your computer simply double click the compile bat batch file in the C1 root_ folder refered to section to compile the source codes 3 If you have ported the modified ADEP generated source codes on an OS other than Windows open the compile bat file which would look something like the code listing 3 6 The line that starts with g O3 in code listing 8 6 is the compile command change the directory of the files in this command and copy 49 and run this command in your OS and the source codes will be compiled to the executable SET PATH SET PATH C Program Files ADEP MmGW bin SET LIB SET LIB C Program Files ADEP MmGW lib SET INCLUDE SET INCLUDE C Program Files ADEP MmnGW include g O3 Wall o C Documents CON DO BW YS FR pause Listing 3 6 Code Listing for compile bat After you have successfully compiled the source codes run the executable adep exe Figure illustrate the adep exe as it is running current generation fitness 27 28 current generation fitness 27 28 current generation fitness 27 28 current generation fitness 27 28 current generation fitness 27 28 current generation fitness 27 28 current generation fitness 27 28 current generation fitness 27 28 current generation fitness 27 28 current generatio
31. 20 000 Jp vex rien best known solution 4950 000 E inta P Roulette whee avg Gap 0 606 mf simple Tournament EEE 40 606 Bs Ready NUM Figure 4 8 The Fitness VS Generation chart and the StatisticInfo table showing perfomance measure of the generated algorithm after the test running 74 4 1 3 Understand the statistics measure generated by ADEP during the test run of 100 Queens Problem Now let us spend some time to understand the statistics produced by test running the Hybrid GA with integer permutation on the 100 Queens problem Firstly we turn our attention to the Fitness versus Generation chart shown in figure which shows the change of objective value of the global best solution against the generation number The Chart can be saved by selecting the menu File Save from the Fitness VS Generation chart window In the Fitness VS Generation chart obtained by test running the hybrid algo rithm on 100 Queens problem the curve shows a ascending trend indicating that the Hybrid GA is improving the solution quality the ascending gradient decrease at later generations which is logical since at the later generations the solution quality is al ready quite good and to look for solution with quality better than the currently found one will be more and more difficult the maximum objective value obtained is only 4920 which is smaller than the optimal 4950 that we are looking for suggesting that
32. 67 143 SI 2 Create Benchmark dialog 200025000 67 3 The Benchmark Configuration Dialog 68 A Settings Entered for the 100QueensBenchmark configuration 69 oe eae Oe Se ee ee Se eae Ee ae Ee ee ee SE 70 4 6 TestBench Manager with the Ex NQueenProblem selected in the Ne ee ee ee ee ee ee ee 72 7 The Run dialog with Ex NQueensProblem and 100QueensBench marks selected 0 0 0 a pe ee eee 73 8 The Fitness VS Generation chart and the StatisticInfo table show ing perfomance measure of the generated algorithm after the test running 74 9 The Fitness VS Generation chart obtained by test runing the hybrid GA on 100 Queens Problem 004 76 LO StatisticInfo table obtained by test running the hybrid algorithm on 100 Queens Problem 2 44 0e 06 4844 45 6 444 4 e544 688 3 77 11 Screen shots at the end of the program execution of adep exe when run iroi tolder C2 on eek ee eee eae ee eee ee eS ee eH 79 12 The files and folders in the root_ folder C2 generated by the ADEP Ee vee ee re ee 80 A A eo aeeuea 81 4 14 Operator Tree of the Population Initialization functional block 83 4 15 Random Operator Node being selected in the Functional Block Panel 84 4 16 Operator Node Description dialog 86 ss eb 90 T 18 Operator Node Configuration dialog for the Medium operator node under Population
33. ADEP USER MANUAL ADEP 1 0 USER MANUAL COMPILED BY XIANSHUN CHEN INTELLISYS CENTER ST ENGINEERING SINGAPORE Overview Introduction This is a user manual about ADEP Algorithm Development Environment for Problem Solving ADEP is a Problem Solving Environment for configuring meta heuristics for solving real life combinatorial optimization problems it was developed to address the need for rapid generation of efficient algorithms that target the real life problems Who Should Read This Manual This manual assume its reader has some background in programming and some basic understanding in C or Java programming Source codes generated by ADEP are Object Oriented source codes that can be in any languages Currently ADEP supports code generation in C and Java To get the most from this manual you should have some understanding of the C or Java algorithms and data structure and some Object Oriented Programming concepts such as class and methods If you are just starting out you will still be able to use this book although you should consider acquiring a C or Java tutorial ADEP generated source codes were designed to be capable of parsing XML by incorporating XML parser in the source codes We include a short introduction to XML How This Manual Is Organized Contents 1 Getting Started 7 1 1 What ADEP is 002000000000000000 000000084 7 1 2 What Needs Does ADEP Fullfile 2 0 000000200000000 7
34. ATLab has one too then why should I choose ADEP Well You should choose ADEP because ADEP does this job MUCH better than other available libaries there are many reasons some of which can be seen as that ADEP combine many benefits and advantages of those available packages other can be seen as useful feasible only available in ADEP First of all all any of those PSE and package are as extensible as ADEP itself The 3 tier structure makes the system high extensible from many different aspects such as compiler installation language installation algorithm installation Many libraries such as GALib are just libraries and are basically only useful for Genetic Algorithm algorithm expert with some intermediate level of programming skill and have been spending some time to study the document of the library they do not have the fancy look of the intuitive GUI of ADEP cannot perform run test and automatically generate statistics does not have automatic configuration engine moreover when a libary whose name read like GALib you know that they won t include other meta heuristics algorithm such as Simulated Annealing Tabu Search or ACO Other PSE such as TOMLAB optimization PSE of MATLAB or HEEDS stands for Hierarchical Evolutionary Engineering Design System although incorporating var ious optimization techniques including genetic algorithm GA and with user friendly interface for exploring various optimization tools for solving a myria
35. How to Solve an optimization problem effectively 34 3 3 2 What is The 8 Queens Problem and What are its constraints 35 3 3 3 How to Formulate 8 Queens Problem Solution as Integer Permu a E E a ats 35 m e es e ee oe ee Se eee Sees a Ae 38 40 3 4 1 How to Locate and Open the Problem h File AO 3 4 2 Understand problem xml and Problem lt T gt readInput method 42 3 4 3 Understand _ evaluate method and How Objective Function Is Implemented in the Method 46 3 4 4 Compile and Run the Modified Source Codes for 8 Queens Problem 49 3 5 Obtain Solution from ADEP algorithm 51 3 5 1 Obtain Solution from results xml 0 0 a a a a a a a aa 51 3 5 2 Obtain Solution by overriding Problem_ Base lt T gt interpret in tbh bE eS 32 HS BS 4S 55 lem_ Base lt T gt record_individual in Problem lt T gt class 58 Peres ee eee ee Pe ee re ee 62 3 6 Solve a N Queens Problem 00 02005 63 4 Configure ADEP Algorithm 64 4 1 How to Test Run algorithm on 100 Queens Problem 64 4 1 1 How to Create Problem TestBench project and upload files to o gt esd ee Ae ae eee ee A ere go ee wee aoe 66 4 1 2 How to Test Run a ADEP TestBench project 71 4 1 3 Understand the statistics measure generated by ADEP during the test run of 100 Queens Problem 75 4 1 4 What are the Files and Folders generated during ADEP Test
36. Individual lt T gt object can represent a solution not matter how is the solution represented In the case of Hybrid GA with integer permutation representation however one Chromo some lt T gt object is sufficient to represent the entire integer permutation which is a solution Therefore in the ADEP generated code as listed in the reference chro mosome will be representing the integer permutation x in the equation 3 1 Let us now move to the source code below the comment action 2 in the code 47 Oo ON anA wn rr b O e ee eC a a a F O Oo WAN DTP WY F CO listing a local variable chromosomeLength is created and assigned the value of the size of chromosome For the users who are wondering what value will be for 8 Queens Problem the variable chromosomeLength 8 in the case of 8 Queens Problem the ADEP generated Hybrid GA algorithm has taken care of reading in the chromo some_ length as declared in the problem xml refer to section 3 4 2 and making correct use of this value Now that we have the chromosome and chromosomeLength declared in the source codes of _ evaluate method that represents the integer permutation as well as the permutation length we can start to implement the objective function in equations and This should be pretty straightforward for anyone with some experience in C or C programming language The code listing 8 5 lists the modified source code of _ evaluate method with the 8 Queens objective function imple
37. Offspring Producer Parent Selection Parent Selection Method Roulette Wheel double clicking the operator node and select the radio button in the Operator Node Configuration dialog that pop up and then close the dialog The rest of the configuration is left as an exercise to the users as they take basically the same steps as the above processes When the configuration is done test run the 100 Queens Problem again refer to Section 4 1 on How to do the test run Chart Fitness VS Generation imulation 0 Fitness YS Generation Figure 4 22 Fitness VS Generation Chart display for the 100 Queens test run after the configuration figure shows that the solution quality found by the algorithm improves from 4922 to 4947 figure shows that the solution with fitness 4947 is obtained after 4 500 seconds is longer than the default configuration since the algorithm is now allowed run 6000 94 StatisticsInfo Simulation Run at Fri Jun 13 12 07 54 2008 Number of Simulation 1 avg CPU time ms 4500 00 min CPU time ms 4500 00 avg Generations 2510 min Generations 2510 avg Fitness 4947 000 best Fitness 4947 000 best known solution 4950 000 avg Gap 0 061 min Gap 0 061 Figure 4 23 Statistics Info table display for the 100 Queens test run after the con figuration generations instead of the default 2000 and the population size also increases Although the improvement of fitness has been observed after the co
38. Selection dialog The default configuration of ACO algorithm in ADEP is the Ant Colony System We will discuss the mechanism involved in each functional block as shown in the work flow of default configured ACO algorithm 1 Map Initialization in this functional block the state map is created an an initiail pheromone To is deposited on each arc between any two states that an ant might traversed 111 2 Ant Reset This is the start of a ACO generation a population of ants are generated and each ant is randomly placed at a state initially 3 Tour Construction In this functional block each ant in the population is set to wonder on the state map to create an ant tour the process of ant tour construction is described in the following pseudo code for i 0 to N 1 for each ant in ant_ population Do state_transition ant end for end for where N is the total number of states that an ant can possibly reached In the state_transition method ant checks if it can move from its current state r to any other unvisited states If no then ant stops and its tour is considered to be completed If yes ant select the next state s to move according to proba bility p r s The state transition probability p r s is determined by using the so called pseudo random proportional state transition rule In pseudo random proportional state transition rule a random number p between 0 and 1 is gener ated and compared with Qo a constan
39. This was realized by the automatic algorithm configura tion engine in ADEP by using this engine the user only need to specify the objective function of the problem and the algorithm take over the task of algorithm configu ration to automatically look for algorithm configurations that achieve the optimum performance It can be seen that with ADEP the highly complicated and tedious process of algorithm design and implementation as well as configuration is almost taken over by the PSE this makes the process of solving complex real life problem an almost RAD Rapid Application Development process even for people who are not experienced problem domain expert or experienced programmers 11 1 3 What Features Does ADEP Have Some of those features have been briefly mentioned in and 1 2 5 there are nu merous available features in ADEP to help the user design and implement as well as test run algorithms some of the main features are listed below and illustrated in the subsequent chapters 1 3 1 Intuitive GUI ADEP features a highly intuitive Graphical User Interface as illustrated in Hybrid GA integer Permutation cpp Population Initialization Population Updating Offspring Local Search Offspring Evaluation hal ral rs Population Evaluation Local Search Stopping Condition Offspring Producer Offspring Mutation Algorithm Panel EER E Hybrid GA End Block Stopping Condi
40. Tour the ant tour that has the highest fitness is selected from all the ant tours generated by the current ant population if the fitness of the best ant tour is greater than the fitness of the global best ant tour obtained so far the global best ant tour is updated to the best ant tour generated by the current ant population Termination Condition this functional block determine whether the algorithm should terminate and terminate the algorithm when certain condition have been fullfilled Pheromone Update The pheromone on each arc between any two states in the 113 state map is updated by using the global best ant pheromone update rule T r 8 1 a x r r s a x Ar r s 5 4 where r s tourg Ar r s a 5 5 otherwise In Equation 5 5 Lg is the number of states visited by the global best tour tour gp 5 3 4 Simple Random Search Simple Random Search Integer Permutation cpp Randomize Population Evaluation Local Search Stopping Condition oOo OoOo Figure 5 9 work flow of Simple Random Search displayed in the Diagram Panel Figure 5 9 shows a Simple Random Search algorithm this algorithm can be easily configure as a multple individual local search algorithm or a multiple random generated algorithm or the combination of both we will briefly go through its functional blocks 1 Randomize this functional block generate a population of randomly generat
41. ach usually taken by researchers when working with a Genetic Algorithm library package such as GALib or TOMLab You will get a lot out this approach by investing heavily in understand the GA paradigm and imple mentation while GALib or other GA library saves you times to code many of the modules The downside is that the learning curve is steep and you want to solve your problem urgently ADEP GUI mode Through the GUI of ADEP you can visually configure the algorithm and run the test on the algorithm to the point until you are satisfy with the results produced by the ADEP configured algorithm To make this an easier process you can upload your modified Problem h file as well as other data files into the ADEP environment and have the algorithm automatically combine the files into the project when compiling and test running this allow the user to quickly add in or remove an advanced operator modules or change a parameter without the need to understand how the coding is done In this chapter we will basically focus on the ADEP GUI mode As discussed in section 1 3 6 the tranditional way of configuring and then testing the performance of an algorithm on a problem can be quite tedious when this process is to be repeated many times what ADEP GUI mode offered is a much faster and more convenient way of configuring and test running an algorithm ADEP GUI mode is able to complete this process by using the project concept The concept wor
42. ading and analysing data from the 78 results xml file described in section the adep exe compiled is able to write the simulation resuls of as many simulations as possible into the results xml file as long as it is not deleted before adep exe is run again 2h Nanyang Technological University Singapore Global University of Excellence Microsoft Internet Explorer Chart Fitness VS Generation Ex Eladep exe File and Folder Tasks benchmarks Gladep sin D console ladep veproj a sane Bev doe Blatgerthm information xml GB Move this fie Qelements Bichartexe T Cony this file I functors 8 Chart exe intermediate manifest Publsh this fie to the I gobal_solution_records Blond bat Web Oman Pcompie bat operators marenie problem B problem mi tiny Byresuits htm tities E resutts xmi MBladep dsp Dstatisticsinfo exe adep dsw Generation 103 6 206 2 308 8 411 4 514 0 616 6 719 2 821 8 924 4 1027 Fitness VS Generation Strategising with substance CN Yang Scholars Programme StatisticsInfo Research Highlights Latest features from Research Hub Simulation Run at Thu Jun 12 19 29 06 2008 Top research news Number of Simulation 2 Nanyang Presidents EET mA Daiso AE a D y CONVOCATION wi je talents are nin CPU time ms F avg Generations 1024 min Generations 1021 avg Fitness 4920 000 best Fitness 4920 000 best known solution 4950 000 avg
43. ally place a dec imal point in the binary section treating the first bit of the binary string section as the sign bit again using the binary string in 8 2 which is then divided into two binary string sections as in and The first bit in each section determines the sign of Be if the first bit of the section is 1 then the decoded lt 0 otherwise the decoded B gt 0 and we place the decimal point at the middle of the binary string section Using this decoding method the binary string section as in 8 3 can be decoded as Gy 1 1 0 1 1 01 1 2 0 27 1 277 1 25 And the binary string section as in can be decoded as B 1 0 1 0 0 10 0 2 1 27t 0 27 0 5 In this case the upper and lower bound for the two parameters are Bomar Biman Ol1 1 1 1 11 1 2 1271 1 27 1 75 and 123 Borin Pronin ILLL 1 11 1 2 1 27 1 27 1 75 If Bo and i have different upper and lower bounds their range can be determined by changing the place between two bits where the decimal place is being inserted 8 3 2 Define the Objective Function for Simple Linear Regres sion Now that we know how to decode a individual solution of binary string chromosome into the value of Bo and Bi we need to define an objective function to assign a fitness to the solution We define the objective function using the Least Squares method With the objec tive value for the solution as b
44. always display updated information about the selected node in the tree control The intuitive GUI allow an user with some fundamental understanding of an algo rithm to quickly figure what each parts of the algorithm accomplish and behave and quickly reduces the learning curve of the software 1 3 2 Automatic Generation of Source Codes ADEP can generate highly efficient and complex algorithm complete complete project files in VC6 and VC2005 as well as makefile with just one click of button by clicking the Generate button on the Command Panel the source codes generated can be in any language due to the way ADEP was designed with current ADEP version supporting the generation of C and Java source codes the source codes generated share highly similar framework albeit the languages of implementation are different and the codes were tested numerous times for cross platform compatibility so that they are run on machines with different platform and operating systems 1 3 3 Highly extensible algorithm framework ADEP has a highly extensible algorithm framework it incorporates a 3 layer architec ture in which the actually code implementation is hidden by layer of XML database the XML data is a distributed tree structure file system consisting of many XML files linked by execution order and relationship defined as rules in the ADEP environment 13 ADEP environment communicate directly with the XML database layer but without knowing wh
45. another IDE such as Microsoft Visual Studio or Borland C Builder when the user generate the C source codes by clicking the Generate button on the Command Panel a batch file containing the compilation scripts is also generated in the same folder where the generated source codes reside To compile the source simply double clicking the batch file if the user is using Windows as the OS or copy and paste the content in the batch file to the command line of the console if the user is using other OS and press ENTER an executable file will be generated as the batch file calls the embedded compiler in ADEP 14 1 3 5 ADEP Has Built in Java Compiler ADEP also has built in java compiler so that user do not need to install Java SDK or Java runtime in order to compile and run the ADEP generated java source codes the ADEP built in java compiler automatically compile the java source code into executable file this also make the execution of the algorithm faster now that the source code is compiled or native machine code instead of java bytecode indeed ADEP compiler driver architecture to be described in the later chapters allow incorporation of any type of compiler for any language into ADEP without the need to modify the source code of ADEP which makes the system highly extensible for incorporating other programming languages 1 3 6 ADEP allow configured algorithm to test run in the ADEP ADEP allow user to upload their objective function i
46. antages of loading algorithm settings from external XML file is obvious when it comes to use the algorithm to solve another problem for example instead of solving the 8 Queens problem the algorithm is asked to solve the 9 Queens problem the compiled source codes for 8 Queens problem does not need to be modified and recompiled all that is needed is to open the problem xml file and edit the chromosome _ length setting in the XML file When this is done run the pre viously compiled source code and the correct solution will automatically be generated for 9 Queens problem instead of 8 Queens problem Now we have gone through a detailed discussion about read nput and prob lem xml let us start to work on the 8 Queens Problem below is the modified prob lem xml file for the 8 Queens Problem lt xml version 1 0 gt lt problem name 8 Queens Problem gt lt overview gt lt chromosome_length value 8 gt lt best_known_ solution existed true value 28 gt lt maximization value true gt lt overview gt lt parameters gt 45 11 12 13 o oo N na A UUN e H a lt parameters gt lt problem gt Listing 3 3 Code Listing for problem xml prepared for 8 Queens Problem In the problem xml file prepared for 8 Queens Problem shown in B 3 the best_ known_ solution value is set to 28 this is the optimal objective value for 8 Queens problem since the 8x 8 1 28 mari 7 A maximum nu
47. ap Step is selected 96 Chart Fitness VS Generation Simulation 0 5 0 6 0 7 0 Fitness YS Generation Figure 4 26 Fitness VS Generation Chart for test running 100 Queens Problem after selecting Two Genes Swap DFL StatisticsInfo Simulation Run at Number of Simulation avg CPU time ms min CPU time ms avg Generations min Generations avg Fitness best Fitness best known solution avg Gap min Gap Fri Jun 13 12 32 38 2008 1 1516 00 1516 00 11 11 4950 000 4950 000 4950 000 0 000 0 000 Figure 4 27 Statistics Info table for test running the 100 Queens Problem after Two Genes Swap DFL is selected 97 figure 4 27 shows that the optiaml solution is obtained in 1 5 seconds which is way faster than the previous configuration that obtain the optimal solution The above shows 3 configurations each of which improves the solution quality of the final solution obtained by the configured algorithm with the last configuration obtained the best results in terms of solution quality and times spent But this is by no means all the configurations that are possible to be tried out and there might be even better configuration than the last configuration shown above 4 2 6 How to Save a Configuration What the user will notice is that whenever the user make changes to the current configuration the configuration setting change and the previous configuration cannot be kept Moreover when the user
48. are about in figure 1 adep dsw adep dsp these are the Visual C 6 0 workspace and project files they can be used to modify and compile the ADEP generated source codes in Visual Studio 6 0 2 adep sln adep vcproj these are the Visual C 2005 workspace and project files they can be used to modify and compile the ADEP generated source codes in the Visual Studio 2005 3 makefile the make file can be used on other OS to compile the ADEP generated source codes 4 compile bat this is a batch file that contains the compilation scripts to compile the ADEP generated source codes The reason that this file is generated is for 33 the user who does not have any compiler installed in his computer in this case none of the adep dsw adep sln or makefile is of usage Since ADEP comes with built in compilers the compile bat simply invokes a user specified built in compiler remember the steps performed in the Generate Source Codes dialog in section to compile the source codes after the user add in the problem specific evaluation function into the source code 5 problem xml this is an xml file that contains the specified XML configuration settings for a problem instance By default three information about the problem instance is contained in this file chromosome length search direction and best known solution found in the past The details of this file will be further explained in section 6 the rest of them are folders that co
49. ates a temptative move that can transit the current solution s to another solution s in the neighborhood of s If this tempta tive move is not tabued a move is defined as tabued if its tabu value in the tabu list is higher than a threshold value or the move pass some aspiration criteria for example the solution s reached from the current solution s by the move has a fitness value higher than the current solution s in either case the fitness different Af f s f s is recorded After a neighborhood of s of certained defined size has been searched the temptative move movejes that produce the highest Af move is selected to be the next move and is recorded for s Perform Move in this functional block for each solution s in the population if the movepest is available for s the move is performed to transit s to its neighboring solution s and the tabu value of move in the tabu list is increased by an amount known as tabu tenure and the move is tabued usually moves that move cannot be selected at least in the next tabu tenure steps Update Tabu List in this functional block the tabu list is updated usually meaning all the moves recorded in the tabu list have the tabu values decreased by 1 so that after tabu tenure generations the move that is tabued in the current generation can become non tabu move again Update Global Solution in this functional block the best individual solution in the current populat
50. be used in the algorithm 2 Priority Code used for internal node keeping and the user does not need to pay particular attention to it This code can be understood as a code that is used to indicate the execution order of each operator node in the operator tree For example the operator nodes Initialization Method and Population Size are at the same node level of the operator tree but Population Size has Priority Code AAA whereas Initialization Method has Priority Code AAB therefore Population Size operator will be executed before Initialization method in the al gorithm generated by ADEP actually we define the operator precedence rule using the full Priority Code of the operator node Since the Population Initial ization functional block also has a Priority Code AAA the full Priority Code 84 for Population Size is AAA AAA whereas the full Priority Code for Initial ization method is AAA AAB When we compare the Random operator node under Initialization method and the Low operator node under Population Size they are also at the same node level and both have Priority Code AAA but the full Priority Code of operator node Random is AAA AAB AAA whereas that of operator node Low is AAA AAA AAA therefore operator node Low is executed by the ADEP generated algorithm than operator node Random 3 Node Id a unique id assigned to each node and is used for internal node keeping The user does need to understasnd its mechanism
51. blem _Base lt T gt console 4 Qcsv_doc public A elements functors lt summary gt E main usage constructor fff lt summary gt Problem Problem _Base lt T gt CR CECR 2 2 8 E operators problem 4 M DefaultProblemFactory h T0D0 initialize the user defineD data structure here an E Problem_Base h E ProblemFactory h 44 lt summary gt E XmIProblemReader h 4 usage destructor E tinyxml 444 lt summary gt E utilities virtual Problem E Resource Files D T0D0 remove the memory used by the user defined data structure here Ba ClassView FileView fi LoS SIBBALD B C Documents and Settings Xianshun Desktop C1 problem Problem h Notepad File Edit Search View Format Language Settings Macro Run TextFX Plugins Window 6S R E268 4h Oc me S B E E1 Problem h public lt summary gt usage constructor lt summary gt Problem Problem Base lt T gt TODO initialize the user defineb data structure here lt summary gt usage destructor lt summary gt virtual Problem TODO remove the memory used by the user defined data structure here Ln 1 Col 1 Sel 0 Figure 3 10 Problem h file opened in notepad 41 there are two method readInput and _ evaluate The readInput method is to ini tialize the problem specific data while the _ evaluate method is the default obje
52. ctive function The details of readInput method and _ evaluate method are explained in the comments as well as the accopany Code Library Help chm document 3 4 2 Understand problem xml and Problem lt T gt readInput method Since we have understood the integer permutation representation for a solution in N Queens as well as how the objective function for 8 Queens can be defined we can implement the objective function in the Problem lt T gt _ evaluate method But before we go into that there are algorithm configuration that we need to take care The following list the source code contained in the Problem lt T gt readInput of the Problem h file virtual bool readInput const char filename Xm1ProblemReader reader reader load data from the ml file if reader loadXmlDoc filename debug lt lt failed to load _ lt lt filename debug endl return false reader action 1 if reader isBestKnownSolutionAvailable this gt set Best KnownSolution reader getBestKnownSolution reader action 2 42 20 21 22 23 24 25 26 27 28 o ON oOo FW WH KF a a a p a a oa A O N e O this gt setChromosomeLength reader getChromosomeLength reader action 3 this gt enableSearchForMaximum reader isSearchForMaximum TODO load other data from input files or do other initialization here return true Listing 3 1 Cod
53. d of optimization 17 problems being addressed Those environements are essentially simulation environ ments Though various algorithms can be configured and executed efficiently in these environments the execution depends on the entire system For many applications which require embedded real time solver this class of environments does not offer the flexibility to configure an efficient stand alone program albeit a turnkey problem solving algorithm Moreover PSE like TOMLAB require expensive third party soft ware such as MATLab Other PSE was developed in Java with nice facilities to output test run results and performance statistics but they were also designed mostly with simulation in mind with little freedom for configuring efficient stand alone program ADEP has the freedom to generate C source codes whenever it needs and even its java code can be compiled into executable moreover the automatic configuration engine is rarely offered by any other PSEs available the source codes generated by ADEP are totally decoupled from the ADEP environment whereas many Java GA PSE requires its own presence as well as the Java Virtual Machine to run ADEP generated source codes and the generate automatic configuration engine are highly portable which makes ADEP virtually cross platform the source codes framework were designed using Design Patterns making them highly structured From the above discussion we can also see than many of the useful
54. define the data structure for the problem here CSVDoubleDocument m_ samples E Listing 8 2 Add member variable m_ samples to Problem lt T gt class Add source codes into Problem lt T gt readInput below the comment line TODO load other data from input files or do other initialization here so that m_ samples can load the data from root_ folder data samples csv The modify source codes for Problem lt T gt readInput is shown figure virtual bool readInput const char filename 1 XmlProblemReader reader reader load data from the sml file if reader loadXmlDoc filename debug lt lt failed _ to load _ lt lt filename 127 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 debug endl return false reader action 1 if reader isBestKnownSolutionAvailable this gt setBestKnownSolution reader getBestKnownSolution reader action 2 this gt setChromosomeLength reader getChromosomeLength reader action 3 this gt enableSearchForMaximum reader isSearchForMaximum TODO load other data from input files or do other initialization here bool found false const char csv_file_name reader getParamValue csv found if found m_samples LoadFile csv_file name else debug lt lt failed_to_find_ parameter _csv_in_the_ lt lt
55. dividual solution in the population 4 Anneal the main mechanism of Simulated Annealing known as Metropolis pro cess is executed in this functional block the Metropolis process runs on each individual solution in the population We illustrate the Metropolis process on an individual solution s as follows for i 0 to M 1 s neighboring _ solution s Af fitness s fitness s if Af lt 0 then if fitness s gt fitness Spes then Stest S end if saa else r rand 0 1 if r lt exp 22 then s s end if end if end for where Spest is the global best solution of the algorithm s is the neighboring solution generated from the current solution s by mutation M is call the Monte Carlo steps T is the annealing temperature of current solution s The default setting for the Disturb Mechanism that mutate the current solution s to obtain the neighboring solution s is Two Genes Swap in which two genes are randomly selected from the integer permutation chromosome of s and swapped 108 5 Lower Temperature this functional block applied the cool schedule for the an nealing tempature T of each individual in the population The default setting for the Lower Temperature is Multiplication which is the a cool schedule that set the new annealing temperature T for a solution s by T Ts xa where a is a value close to 1 but is smaller than 1 5 3 2 Tabu Search Jabu Search Integer Permutation cpp
56. e Ja outfile lt lt III Na outfile close Listing 3 12 Code Listing for Problem lt T gt record_individual method reimple mented Now we recompile the source codes and run the adep exe After adep exe is done running you should find a new folder global_solution_records is placed in the 61 Oo Ont anA UN Fk m a j N e root_ folder in this folder there are the generation changed solution files with file names generation dat generated by the algorithm using the format as specified by Problem lt T gt record_individual code listing shows the content of one of those file with file name generation6 dat Current Generation 6 Solution Objective Value 27 ILILILILIL ILLI Queen 0 row 0 col 6 Queen 1 row 1 col 0 Queen 2 row 2 col 5 Queen 3 row 3 col 1 Queen 4 row 4 col 4 Queen 5 row 5 col 2 Queen 6 row 6 col 7 Queen 7 row 7 col 3 PILULU Listing 3 13 content of the file generation6 dat in the global solution_ records folder 3 5 4 Obtain Solutions for the Entire Population of solutions for each Generation There is also ways for the user to print the entire population of solutions at each gen erations to files by overriding Problem_ Base lt T gt record_population in the Prob lem lt T gt class declaration Of course to print all those data is computationally very expensive and requires user to have sufficient disk space norma
57. e 4 7 select a root_ folder to stored the gen erated source codes by Pressing the Browse button and then select a compiler from the Compiler drop down list When done click OK ADEP will automatically perform the following task in order 1 generate the source codes of the algorithm combined with the files in Ex _NQueensProblem project folder and store them int the root folder specified in the Run dialog earlier assume the user selected the root_ folder to be C2 2 compile the source codes in the root_ folder C2 3 run the compiled adep exe file 4 display the statistics in the Fitness Versus Generation chart and the Statis ticsInfo table as shown in figure E Untitled ADEP Chart Fitness VS Generation 4920 01 iin a Simulation 4917 1 4914 21 4911 31 4908 41 4905 51 4902 61 4899 71 brid GA 4896 81 Di 4893 91 4891 000 Gpneration 10 103 6 206 2 308 8 411 4 514 0 616 6 718 2 821 8 924 4 1027 Fitness VS Generation Statisticsinfo Simulation Run at Thu Jun 12 18 08 03 2008 Block Offspring Producer Number of Simulation 1 a resan IP escaing avg CPU time ms 313 00 of Some tune a E Parentselecton fata Poo Sie 3 avg Generations 1027 min CPU time ms 313 00 min Generations 1027 g medium avg Fitness 4920 000 5 Parent Selecton Method best Fitness 49
58. e Listing for ADEP generated Problem lt T gt readInput method The source codes in 3 1 will be explained line by line here In line 1 of source codes 8 1 the virtual method readInput is declared with a const char parameter which specifies a file name This parameter is the problem xml file that is briefly described section 3 2 that means whatever information that is contained in problem xml file we will make use of in the algorithm Before we go on to describe other source codes Let s take some time to understand problem xml file first below shows the problem xml file generated by ADEP lt xml version 1 0 gt lt problem name problem gt lt overvlew gt lt chromosome_ length value 15 gt lt best_known_ solution existed true value 0 gt lt maximization value true gt lt overview gt lt parameters gt lt param lt param lt param lt param lt param name dummy1 name dummy2 name dummy3 name dummy4 name dummy5 value 0 type int gt value 0 type double gt value true type bool gt value false type bool gt value dummy type string gt 43 b 16 17 lt parameters gt 18 lt problem gt Listing 3 2 Code Listing for problem xml In the code listing of the problem xml in 3 2 there are two sections the lt overview gt section contains the algorithm setting while the lt parameters gt section specifies t
59. e Listing for problem xml prepared for 100 Queens Problem Now rerun the adep exe without recompiling the source codes and you should get the solution for the 100 Queens problem before rerunning adep exe delete the global solution_ records folder and the results xml The source codes for this chapter is included in the ADEP as an example it can be found at to be fill later 63 Chapter 4 Configure ADEP Algorithm In this chapter you will learn 1 How to Configure an algorithm to improve its performance 4 1 Howto Test Run algorithm on 100 Queens Prob lem If you have followed through the Chapter 3 and worked on the examples thouroughly you will notice that you would not usually get the global optimal solution for the 100 Queens Problem This implies that the algorithm that is generated by ADEP is not optimized for an N Queens Problem by default and therefore you need to configure the algorithm to optimize it for the N Queens Problem There are two ways to do this 1 expert mode a get the documentation to study the algorithm source codes generated by ADEP b study the books on Genetic Algorithm c then study the books on Genetic Algorithm that solve integer permutation representation problem d then begin to tweak the codes generated by ADEP to configure the algo rithm 64 e refer now and then if you are not familiar with C and its standard template class implementation This the appro
60. ed individual solutions if the population has not been created or mutate the indi vidual solution if the population exists already optional 2 Population Evaluation this functional block assigns a calculated objective value to each individual solution in the population 114 3 Local Search Local search to be applied to the individual solution in the popu lation optional 4 Stopping Condition control the termination of the algorithm by using different configuration the Simple Random Search algorithm can be changed to a single solution local search or a multiple individual local search or a multiple solution mutation improving algorithm and so on 115 Chapter 6 ADEP Example Quadratic Assignment Problem The quadratic assignment problem QAP is one of fundamental combinatorial opti mization problems in the branch of optimization or operations research in mathematics from the category of the facilities location problems The problem models the following real life problem There are a set of n facilities and a set of n locations For each pair of locations a distance is specified and for each pair of facilities a weight or flow is specified e g the amount of supplies transported between the two facilities The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows The problem statement resembles that of the
61. ed Annealing from the algorithm drop down list Notice that the information panel at the bottom automatically updates and display a brief paragraph describing Simulated Annealing algorithm this is shown in figure With Simulated Annealing selected in the algorithm drop down list click OK The user is brought back to the ADEP GUI but this time The Diagram Panel shows the work flow of the Simulated Annealing algorithm as shown in figure With the newly selected algorithm framework displayed in the Diagram Panel the techniques discussed in previous sections are all applied 101 Algorithm Selection Currently Configured Algorithm Language cpp Representation Integer Permutation Simulated Annealing Simulated annealing SA is a generic probabilistic meta algorithm for the global optimization problem each step of the SA algorithm replaces the current solution by a random nearby solution if the new solution is better itis chosen whereas if it is worse it can still be chosen with a probability that depends on the difference Figure 5 2 Algorithm Selection dialog with Simulated Annealing selection Simulated Annealing Integer Permutation CPI ss p L n iii i Figure 5 3 Diagram Panel showing Simulated Annealing algorithm workflow after the change in Algorithm Selection dialog 102 5 1 2 Generate and Modify Simulated Annealing Algorithm Source Cod
62. ed Problem h file appearing in the File to Upload text box Next in the Directory drop down list select problem this allow ADEP to put the modified Problem h file uploaded into the corresponding problem folder later during the compiling and testing running stage Always remember that whichever folder under the root folder that you get the modified file from you should also set the folder name in the Directory drop down list edit box if it is in the root_ folder then leave the Directory dropdown list edit box empty if the name of the folder does not appear in the drop down list then try it in the edit box when this is done click OK on the Add File dialog the user is brought back to the Create TestBench dialog with problem problem h appearing in the list box of the 70 Testbench Directory section In Chapter 8 we modified two files problem xml and Problem h But we only uploaded the Problem h file to the Ex _NQeensProblem project folder because the 100QueensBenchmark will be translated into the problem xml file by ADEP during the later compiling and test running stage At this point press the OK button on the Create TestBench dialog and this completes the process to create project and upload files One thing to pay attention although the manual so far only demonstrate Hy brid GA with integer permutation and C programming language ADEP is highly extensive with other algorithm frameworks problem represe
63. ed by test running the hybrid algorithm on 100 Queens Problem EEEN best_ fitness s N 7 avg Fitness where best _fitness s is the best fitness objective value found for the simulation s and N is the total number of simulations min best_ fitness s s 1 N min_search 8 best Fitness max best_ fitness s s 1 N max_search 9 best known solution the fitness value of the best known solution for the 100 Queens Problem this is the calculated optimal fitness value entered during the create of 100QueensProblem benchmark __ avg_Fitness best_known_ solution 10 avg Gap best_known_ solution x 100 __ min_Fitness best_known_solution 11 min Gap best _known_ solution x 100 In case you accidentally close the Fitness VS Generation chart and StatisticInfo table if you are looking for those values recorded in Fitness VS Generation chart and StatisticInfo table you can go to folder C2 the root_ folder that stores the TT generated source codes and the compiled adep exe by ADEP at the time the test run is conducted and active the Chart exe and StatisticInfo exe to view the results again 4 1 4 What are the Files and Folders generated during ADEP Test Run of 100 Queens Problem Figure shows the list of files and folders in the C2 folder Compared the contents of C2 with those of C1 in figure 3 7 of section 3 2 we notice that a few other files are created they are
64. eens 1 2 3 4 5 6 7 8 row 1 2 3 4 5 6 7 col flale b h c gid ee Table 3 1 8 Queens Arrangement in Chess Board In table the Queen 1 is placed in row 1 and col f Now since the Queens row and col symbols are all arbitrary we can use 0 1 7 to replace 1 8 for Queens symbol use 0 1 7 to replace 1 8 for row symbols use 0 1 7 to replace a b c h g and the table becomes Queens 0 1 2 3 4 5 6 7 row 0 1 2 3 4 5 6 7 col 5 0 4 1 6 2 7 3 Table 3 2 8 Queens Arrangement in Chess Board with Redefined Row and Column Symbols In table the Queen 0 is placed in row 0 and col 5 which is actually the same position as in table Observant users at this point would have discovered the integer permutation from table 3 2 The Queen arrangement in table 3 2 can be simply represented by an integer permutation x 5 0 4 1 6 2 7 3 To illustrate how this is possible take x 0 5 and x 1 0 these two equations can be translated to mean Queen 0 is placed at row 0 and col 5 and Queen 1 is placed at row 1 and col 0 And in generate xr c can be translated to mean Queen r is placed at row r and col c In the terminology of Hybrid GA a solution is called a chromosome therefore if the solution is represented as an integer permutation x then we will called a solution x a chromosome and in expression x i v we will ca
65. eing defined as i N 1 i N 1 E amp yi o Bizi i 0 i 0 where N is the number of sample data points Hence the algorithm is to look for the individual solution whose objective value E is minimum the problem become the minimization search 8 3 3 Generate HGA with Binary Representation using ADEP To generate the algorithm with the appropriate algorithm representation and program ming language configure the settings in the Algorithm Selection dialog accessed through the command in the Algorithm Panel as shown in figure Generate the source codes using the settings in figure in the root_ folder that stores the generated source codes create a folder called data 8 3 4 Create and Save sample data in Excel Open Excel application and enter the sample data for x and y and save the file as samples2 csv in the root_folder data folder figure shows the content of the 124 Oo ON nw Fe UN Fe o Algorithm Selection Currently Configured Algorithm Language cpp Representation EMED Binary HGA Generational HGA designed to handle problems that are encoded as binary strings Figure 8 2 Algorithm Selection dialog configuration to generate codes for solving simple linear regression samples2 csv file In the samples2 csv file shown in figure the first column is the data for x and the second column for y 8 3 5 Modify problem xml Open problem xml and edit the file as shown in
66. ere the actually source codes are located and not even aware which language the source codes are written XML database layer acts as a glue between many dif ferent subsystem such as the compiler driven subsystem the source codes the ADEP environment this makes the ADEP environment highly adaptable and extensible To include a new module for algorithm or algorithm operators into the ADEP framework is as simple as copy the source code module into a folder and insert an XML file with links to that source code into appropriate hierarchy of the file system when the next time the ADEP is started the new code module will automatically be available because of this an entire new branch of algorithms written in different languages can be easily incorporated into ADEP without recompiling the ADEP source codes In fact the ADEP environment was originally developed for Hybrid Genetic Algorithm in C but due to its extensible nature of its architecture other algorithms such as Tabu Search ACO and so on are added and even in a different language Java The high extensibility of ADEP framework is also manifest in its source code frame work it is designed such that a user defined objective function source code can be used by any algorithm in its algorithm framework database as long as they share the same representation 1 3 4 ADEP Has Built in C Compilers ADEP has its own built in compilers this means the user of ADEP does not need to purchase
67. es to solve N Queens Problem this part is exactly the same as that for Hybrid GA as discussed in chapter 3 Just follow the same steps to modify problem xml and Problem h file in the root_ folder problem folder 5 1 3 Test Run Simulated Annealing algorithm on the 100 Queens Problem Remember that in Section at which we create a TestBench project Ex NQueensProblem with a benchmark 100QueensBenchmark the project is cre ated in an environment in which Hybrid GA integer permutation representation and C languages are 3 selected settings ADEP s algorithm framework design allow this project to be seamlessly incorporated into other algorithms as long as integer permutation and C languages are the other selected settings In the environ ment that we have just configured Simulated Annealing integer permutation and C language are the selected settings therefore we can use the previously cre ated Ex NQueensProblem project to test run the Simulated Annealing algorithm without any modification required To test run the Simulated Annealing algorithm on the 100 Queens Problem following the instructions in Section That is click on the Run Command in the Command Panel in the Run dialog appear se lect Ex NQueensProblem from the Problem drop down list and 100Queens Benchmark benchmark from the Benchmark drop down list and then selected a root_ folder to store the generated source codes as well as a compiler from the Com pi
68. esign as well as data structures and the users would be happy to know that whatever they have learned in the previous chapters applied to any algorithms with any respresentation written in any language 5 3 Brief Descriptions of the Meta Heuristic algorithms available in ADEP 5 3 1 Simulated Annealing Figure Let me explain what happened at each functional block using integer permutation as the solution representation Simulated Annealing Integer Permutation cpp Population Evaluation Stopping Condition Anneal Lower Temperature o B Ba Figure 5 6 Work flow of Simulated Annealing algorithm in the Diagram Panel 1 Initialization a population of individual solutions are generated such that each solution is a randomly generated integer permutation This functional block also initialize the annealing temperature T for each solution s 2 Population Evaluation this functional block calculate and assign an objective value for each individual solution in the population 107 3 Stopping Condition this functional block determine the Simulated Annealing al gorithm should terminate and terminate the algorithm when certain termination conditions are fullfilled notice it is in a while loop which we have called a gener ation refer to Section 4 2 1 In this functional block the global best solution Sbest 18 also updated if its fitness is found to be less than one of the in
69. est_known_ solution line in problem xml being written as lt best_known_ solution existed false value 0 the algorithm will continue to search until other termination criteria reached The statement below the comment reader action 2 is executed to set the length of the chromosome used in the algorithm Remember from that the length of a chromosome is the length of the integer permutation in an algorithm us ing integer permutation as representation for example in 8 Queens the chromosome 44 Oo ON na BW NY KF rae es length will be 8 The reader object obtain the value of chromosome length from statement in problem xml lt chromosome_ length The statement below the comment reader action 3 is executed to set the search direction of the algorithm The reader object obtain the value of search direction statement in problem xml from lt maximization In some cases user might also want load in some other data from other sources readInput method is a perfect place to start because it is almost the first method to be called by the algorithm To put in user define initialization code just enter them after the comment line TODO load other data from input files or do other initialization here This completes the analysis of the source codes in readInput basically readInput load the algorithm information from problem xml file and used it to initialize parame ters used in the algorithm The adv
70. euristic algorithm that solves a NP hard problem may be far from optimal in terms of performance This is likely due to the fact that the designer may not have the resources or resolve to fine tune the algorithm It is also likely that the programmer may not possess the necessary experience and knowledge on meta heuristics algorithms to effectively make the necessary improvement ADEP was developed to address the need for rapid generation of efficient algo rithms that target the real life problems the user only needs to modify the objective function to convert the codes for solving the target problem As a result the time to implement the bulk of codes for the HGA operators such as crossover mutation parents selection fitness scaling population update etc can be devoted to other more productive solution integration tasks ADEP allows users to focus on the high level problem abstraction significantly reduces the algorithm development time and effort in designing and implementing the meta heuristic algorithm to solve the problem 1 2 4 ADEP Allow Users To Configure An Algorithms Perfor mance towards On a Particular Problem One of the main issues faced by system developers of meta heuristic algorithms is that there seem to be no one size fits all type of search algorithms In other words for any given meta heuristic algorithm with a particular parametric setting it is unlikely that it will perform equally well for all the problems
71. figuration the automatic configuration engine is generated entirely in C source codes by ADEP and then compiled and set to run this is highly advantageous Firstly the engine is written in C source codes that is platform independent therefore the whole engine can be brought to another machine to run regardless of the OS running on that machine Secondly even when the engine is running on the same machine as the ADEP the ADEP can perform other tasks at the time the engine is running without any delay or application hanging issues since the engine and ADEP are now run as two totally independent processes on the same machine Thirdly the engine is exported by ADEP as C source codes the user can modify the engine to suit his need if that is necessary 16 1 3 8 Other Features of ADEP Apart from those features listed above ADEP has many other features such as sav ing configured algorithms not as source codes but as configuration file that can be loaded back into ADEP print current configuration extend different algorithm frame works by adding in new operators view list of configurable parameters and operators extensive instruction and information knowledge for various operators programming language extension and so on 1 4 Why Choose ADEP So ADEP is another PSE to be use for meta heuristic algorithms on optimization problem you may say and nowaday there is abundant libaries and package that does this job and even M
72. g the Generate Run or Learning commands in the Command Panel 85 Node Description ye Operator Description Operator Details Operator Instantiation Codes This initialization method generates a population whose individual chromosome is a randomly generated integer permutation string 0 k Operator Random Update Figure 4 16 Operator Node Description dialog 3 Operator Initialization Code This is the initialization code that will be used by ADEP to do the initialization of the activated operator node during the pro cess of algorithm generation the initialization is editable if you make change the Update command will be enabled but unless the user understand the al gorithm design patterns and flow require the user to be advanced user of the ADEP system it is recommended that the user do not attempt to modify the initialization code 4 2 3 Understand the default configuration of Hybrid GA Now that we have a basic understanding of the Hybrid GA as well as the graphical elements in the Functional Block as well as the Node Information I will explain the default configuration used by the Hybrid GA in each functional blocks The user can refer to the operator tree of each functional block and the operator information as we go along this section 1 Population Initialization 86 a Initialization method is selected as Random indicating the initial population is a set of individual s
73. hapter 1 Getting Started What you will learn in this chapter 1 What ADEP is 2 What Needs Does ADEP Fullfill 3 What Features Does ADEP have 4 Why Choose ADEP 1 1 What ADEP is ADEP stands for Algorithm Development Environment for Problem solving It is a Problem Solving Environment PSE that allow user to configure and generate state of art meta heuristic hybrid algorithms in C or Java source codes for solving various real life combinatorial and numerical optimization problems 1 2 What Needs Does ADEP Fullfile To answer this questions we must clarify what we mean by real life combinatorial and numerical optimization problems and what are meta heuristic hybrid algorithms in 1 1 1 2 1 What Are Real life Combinatorial and Numerical Opti mization Problems Many real life problems in industries and financial markets are essentially optimization problems Optimization refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set An optimization problem can be represented in the following way Given a function f A gt R from some set A to the real numbers Sought an element xo in A such that f xo lt f x for all x in A minimization or f a gt f x for x all in A maximization Combinatorial optimization is a branch of optimization Its domain is optimiza tion problems whe
74. has been copied into Problem lt T gt class declaration in the Problem h file Let us try to analyze how this method does and how the user can 56 Oo ON no FB WY KF H a a a a a a a ND oT FP UNEO reimplement the method to obtain the user desired output solution form The interpret method is automatically called by the ADEP algorithm just before the program terminates with the global best solution passed to the method which is the parameter individual to the interpret method to allow the global best solution to be saved to some form There are many ways that the user can reimplement this method some of the ways suggested will be 1 the user can directly write the GUI code in Problem lt T gt interpret to display the solution individual 2 the user can write the information about the individual to another file with his user defined format Just as a simple demo we are going to output the solution as a table format in a HTML file output htm Code Listing list the source codes that we implements in the interpret method virtual void interpret Individual lt I gt amp individual std ofstream outfile outfile open output htm outfile lt lt lt html gt lt body gt n outfile lt lt lt table_border 1 gt n Chromosome lt T gt amp solution individual 0 int N solution size for int i 0 i lt N i outfile lt lt lt tr gt n s for int j 0 j lt N j if j s
75. he user defined parameter to be loaded by reader in For the moment the lt param eters gt section can be ignored lt overview gt section contains 3 critcal information that is to be read by the algorithm chromosome_ length best_ known_ solution max imization those parameters were explained in the comment of readInput method in the Problem h file In line 3 of source codes an object of class XmlProblemReader reader is created its loadXmlDoc method is called in line 6 is called to load the data into reader The statement below the comment reader action 1 is executed to load in the information about the best known solution found in the past Only the objec tive value of best known solution found in past is of interest to us this objective value can be either a calculated value or obtained by some other algorithms in the past In a sense the objective value of the best known solution can be thought of as the global optimal value that we wish to reach The information about the best known solution found in the past is useful in the sense that if that information is avail able the algorithm is able to terminate when it find this solution if the algorithm is configure to terminate in this way This ensures that no extra CPU is wasted if we already know the global optimal fitness value If no such an objective value infor mation is available when reader isBestKnownSolutionAvailable return false which is resulted from the lt b
76. hmarks section More than one benchmarks can be created for a particular TestBench project by Clicking the Create New Benchmark command 69 File to Upload Directory problem Figure 4 5 Add file dialog to upload files to the Ex NQueensProblem project folder again Remember earlier in our discussion the TestBench project represent the problem while a particular benchmark represent a particular problem instance a created Benchmark can be update or delete by selecting the Benchmark in the list box and pressed the Update or Delete benchmark options also available to the Benchmarks section To test out these functions the user can try to add an 500 Queens benchmarks After the benchmark is created the next step is to update the modified source codes files and other files changed or added to the generated source codes earlier to the project folder First Let us upload the Problem h file that we modified in the chapter Click Add File button in the Testbench Directory section an Add File dialog appear as shown in the figure In the Add File dialog click the Browse to bring up the browse for file dialog navigate to the root_ folder in which the previously generated source codes were stored which is the C1 folder refered in section 3 1 navigate to the problem folder and select the Problem h file When this is done the user is brought back to the Add File dialog with the file path of the select
77. hromosome lt T gt pChrom individual 0 assert pChrom NULL Chromosome lt I gt amp chromosome pChrom assert chromosome empty int chromosomeLength chromosome size assert chromosomeLength lt this gt get ChromosomeLength 129 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 TODO add codes for fitness calculation here double beta0 0 double betal 0 int hl 0 int h2 chromosomeLength 2 int i 0 int hldp 9 double sign0 chromosome hl 1 1 1 for i 1 i lt h2 1 i int index hldp 1 i if chromosome i 1 beta0 pow 2 0 static cast lt double gt index beta0 x sign0 int h2dp h2 9 double signl chromosome h2 1 1 1 for i h2 1 i lt chromosomeLength i int index h2dp 1 i if chromosome i 1 betal pow 2 0 static cast lt double gt index J betalx sign1 double SSE 0 130 46 47 48 49 50 5l 52 53 55 56 57 for i 0 i lt m_samples GetRowCount i double x m_ samples GetValue i 0 double y m_samples GetValue i 1 double y_bar beta0 betal x SSE y y_bar y y_bar objective _value sqrt SSE return objective_ value Listing 8 4 modified Problem lt T gt _ evaluate In the code listing the local variable SSE is the sum of squared errors m_ samples GetR
78. in compiler to compile and run the configured algorithm within the ADEP 10 environment that relieve the user the copy and replacement manual operation during the numerous algorthm testing 4 charts and algorithm performance stastics displayed once the configured algo rithm complete its run 5 automatic configuration engine for automatic algorithm configuration to be dis cussed in 1 2 5 1 2 5 ADEP Can Automatically configure algorithms The increasing complexity of both problems and algorithms makes algorithm devel opment and problem solving more and more challenging Conventional algorithm development methodology usually requires significant effort in codes generation and modifications Furthermore the quality of the algorithm depends very much on the designer s experience level of knowledge specific to the problem being addressed as well as the algorithm flow stucture A programmer without profound algorithm design experience will find developing an effective and robust algorithm extremely challenging Not to mention that in practical scenarios users may face with various requirements of the algorithm An algorithm that solves one particular class of problems well may not work for other classes of problems or scenarios at all This makes the algorithm development for complex real life applications even tougher ADEP can take over the user s task of configure an algorithm to make it efficient to solving the problem at hand
79. ing Mutation led ed E 4 Hybrid GA Block Stopping Condition Figure 3 1 ADEP GUI As was explained in Sectiorj1 3 1 about the ADEP GUI the top right corner of the ADEP GUI features the Command Panel which hosts the three main commands of the application Generate Run Learning The Command Panel is shown in the figure The default loaded algorithm is Hybrid GA which is a memetic algorithm frame work The work flow of the Hybrid GA framework displayed by the Diagram Panel as illustrated in figure Notice that at the title bar of the Diagram Panel three different information about the current loaded algorithm framework are displayed the algorithm framework name Hybrid GA the problem representation Integer Permutation and the pro gramming language for the generated source codes cpp The 3 informations dis played in the title bar in the Diagram Panel deserves some explanations 1 algorithm framework typical for meta heuristics algorithm each type of algo 28 Command Panel Figure 3 2 ADEP Command Panel Figure 3 3 ADEP Diagram Panel showing the default Hybrid GA framework work flow 29 rithm usually has numerous different configuration consisting of a wide variety of parameters and opertors those configurations all together for the algorithm framework for a particular branch of the algorith
80. ing row i is not in the same diagonal as the Queen occupying row j The objective function f defined in equation is the total number of not in same daigonal constraint conflicts removed N is the total number of queens which is 8 for 8 Queens problem and z row is the column index for the queen at row i 39 3 4 How to modify the generated C source codes to solve 8 Queens Problem This Section will explain how to add the problem objective function to the ADEP generated source codes so that the generated algorithm can actually solve a problem The following steps are taken 1 How to locate and open the source code files for modification 2 How to understand and modify the source code to solve a problem 3 4 1 How to Locate and Open the Problem h File To add the objective function to the generate source codes the class to which the objective function is to be added should be located this class is stored in the Prob lem h file The following paragraph explains where to locate the Problem h file in the root_ folder C1 Assume that you have VC 6 0 or VC 2005 installed in your computer double click adep dsw or adep sln workspace file to open the ADEP generated project After VC 6 is launched switch to the FileView in the Workspace of the studio navigate to the problem folder in the FileView panel open the folder and double click the Problem h file listed in the folder At this time the Problem h will be loaded
81. ing to represent the solution for the simple linear regression problem shown above the individual solution in the Hybrid GA is a solution that contains a floating string chromosome of length 2 as shown by the example in table 8 5 1 23 34 2 Table 8 5 floating string chromosome in Continuous Hybrid GA to represent Bo and b in this floating chromosome we simple let Bo 1 23 and Bi 34 2 8 4 2 Define the Objective Function for Simple Linear Regres sion The objective function is the same as that defined in section 8 3 2 136 8 4 3 Generate HGA with Floating Point String Representa tion using ADEP To generate the algorithm with the appropriate algorithm representation and program ming language configure the settings in the Algorithm Selection dialog accessed through the command in the Algorithm Panel as shown in figure Algorithm Selection Currently Configured Algorithm Language cpp Representation Continuous i Continous HGA Continous HGA designed to handle problems that are encoded as real valued numbers Figure 8 5 Algorithm Selection dialog showing Hybrid GA with floating string rep resentation Generate the source codes using the settings in figure in the root folder that stores the generated source codes create a folder called data 8 4 4 Create and Save sample data in Excel This step is the same as that defined in section 8 3 4 8 4 5 Modify
82. ion 8 3 8 except the decoding process for Bo and i is not longer needed and therefore removed virtual void interpret Individual lt T gt amp individual TiXmlDocument doc TiXmlElement doc_root new TiXmlElement simple_linear_regression doc LinkEndChild new TiXml Declaration 1 0 doc LinkEndChild doc_ root Chromosome lt T gt amp chromosome individual 0 int chromosomeLength chromosome size double beta0 chromosome 0 double betal chromosome 1 TiXmlElement element _parameters new TiXmlElement parameters element _parameters gt SetDoubleAttribute beta0 beta0 element _parameters gt SetDoubleAttribute betal betal doc_root gt LinkEndChild element_ parameters TiXmlElement section plot new TiXmlElement plot doc_root gt LinkEndChild section_ plot double SSE 0 for i 0 i lt m_samples GetRowCount i double x m_ samples GetValue i 0 double y m_ samples GetValue i 1 double y_bar beta0 betal x TiXmlElement element sample new TiXmlElement sample element _sample gt SetDoubleAttribute x x 140 30 element _sample gt SetDoubleAttribute y y 31 element _sample gt SetDoubleAttribute y_bar y_bar 32 section _plot gt LinkEndChild element __sample 33 SSE y y_bar x y y_bar gir 35 36 section_plot gt SetDoubleAttribute SSE SSE 37 38 doc SaveFile plot xml 39 40 Listi
83. ion is selected and if its fitness value is higher than the global best solution Soest Sbest iS updated to that best individual solution in the current population 110 5 3 3 Ant Colony Optimization The ant colony optimization algorithm ACO introduced by Marco Dorigo in 1992 in his PhD thesis is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs They are inspired by the behaviour of ants in finding paths from the colony to food In ACO the solution of a problem is usually the tour traversed by an ant The tour consists of a sequence of states that the ant visit as that ant wonder on a state map guided by the heuristic cost between two states as well as the pheromone deposited on the arc between two states For integer permutation a state is represented by an integer and a tour is therefore an integer permutation since each state cannot be visited more than once usually Ant Colony Optimization Integer Permutation ACO cpp Map Initialization Ants Reset Tour Construction Calculate Cost Local Search oe Oo Oo o Pheromone Update Termination Condition Select Best Ant Tour Figure 5 8 workflow of the Ant Colony Optimization algorithm displayed in the Dia gram Panel Figure shows the work flow of the Ant Colony Optimization algorithm in the Diagram Panel which is selected by selecting the algorithm in the drop down list in the Algorithm
84. ks like this 1 2 the user first create a TestBench project in the ADEP environment and then the user upload whatever files that he changed in the generated ADEP source codes refer to chapter 3 into the corresponding folders in the created project directory the user configure the algorithm through ADEP GUI and then the user click on Run command on the Command Panel and in the Run Command Dialog that appear select his created project in step 1 ADEP 65 will then combine the configured algorithm with the user modified files in the project and then compile and test run on those hybrid source codes returning the performance statistics when it is done This section started with the assumption that the user is working on the 100 Queens problem and has modified the problem xml and the Problem h file with the source code compiled and run successfully but the user was not able to get the best result that he was looking for He started by reading the next section 4 1 1 4 1 1 How to Create Problem TestBench project and upload files to the project To create a TestBench project select menu Run New Project the Create Test Bench dialog appear which is illustrated in figure In the Create Test Bench dialog in figure 4 1 enter a project name in the Project Name text box for example Let us assume Ex NQueensProblem is entered in the textbox Click on the Create New Benchmark button in the Benchma
85. l block To select a different functional block click on the functional block in the Di agram Panel and it will be selected notice that the Functional Block Panel below the Diagram Panel automatically update the tree control to reflect the operator trees belonging to the newly selected functional block For those users who have already have some basic understanding of Genetic Al gorithm using integer permutation representation they should not have difficulty to understand this workflow But to facilitate the understanding of those users who are new to this field below is a brief introduction of what each functional blocks in figure attempts to do 81 Population Initialization This generates a population of individual solutions each of which is a randomly created integer permutation Population Evaluation This assigns to each of the individual solutions generated in the Population Initialization a fitness value fitness value is different from the objective value in that only the more positive fitness indicate the individual solu tion is better this is different from the objective value assigned to an individual due to objective value having a search direction there are many ways to convert an objective value to a fitness value the simplest way is to invert the sign of the objective value if the search is minimization for maximization simply assign the objective value as the fitness value Local Search This is optional
86. ler drop down list Finally press OK The generated Simulated Annealing with the Ex NQueensProblem project incorporated should be compiled and run suc cessfully figure 5 4 shows that Fitness VS generation chart and the StatisticInfo table displayed when the Simulated Annealing test run on 100 Queens Problem was completed 103 Command Panel fe Ameal Lower Temperature Simulated Annealing mulation 0 Generation 117 0 233 0 345 0 465 0 581 0 697 0 813 0 929 0 1045 0 1161 Fitness VS Generation StatisticsInfo Simulation Run at Fri Jun 13 15 48 32 2008 Block Initialization Number of Simulation 1 E Q titeization ere Initaization avg CPU time ms 29156 00 zd Pm ata min CPU time ms 29156 00 Fima avg Generations 1161 P ream min Generations 1161 Temperature 1ntaiazaton i avg Fitness 4910 000 best Fitness 4910 000 best known solution 4950 000 avg Gap 960 808 min Gap 960 808 Figure 5 4 Fitness VS Generation and StatisticInfo Application invoked at the exit of Simulated Annealing algorithn on 100 Queens Problem 104 5 1 4 Configure Simulated Annealing Algorithm through ADEP GUI This part is the same as that for Hybrid GA in chapter 4 the user with some experience in Simulated Annealing and under the guide of Code Hint as well as the Code Library Help sho
87. ll i an index of integer permutation x as locus and j value at i th index of x as allae Thus in Hybrid GA using integer permutation as representation a chromosome is just an integer permutation with the index of the permutation being called locus and value at the particular index begin called allae 37 3 3 4 How to Define an Objective Value for a 8 Queens Prob lem Solution Now the formulation of 8 Queens problem solution as a Hybrid GA chromosome in the form of integer permutation has been described we need an objective function to define a objective value for each chromosome But first of all what is meant by an objective value for the sake of those users who do not have background in optimization an objective value can be understood as the quality of a solution An objective function is therefore a function that measure the quality of a solution and then assign it an objective value As defined in an optimization problem is to look for a solution whose objective value is maximum or minimum For some problem the objective value can be defined as the cost for example in a travelling salesman problem a solution will be the sequences of cities that the traveling salesman visits in order and the objective value can be define to be the cost of traveling all the cities using the sequences of cities indicated by the solution which can simply mean the total distance travelled when the traveling salesman visit each city according to
88. lly this option is dis abled in the ADEP algorithm but can be enabled through ADEP GUI More about how this can be done will be discussed when it comes to introduce the statistics analysis capability of ADEP 62 Oo ON no FCF WY fF ee a ja wW N e 3 6 Solve a N Queens Problem Now that you are quite familiar with the 8 Queens problems and are able to make use of ADEP generated source codes to solve the 8 Queens problem what if you would like to solve the N Queen problem say 100 Queens problem How should the source code be modified to do that Luckily the source codes require no modification at all the only change is in the problem xml file Suppose that you are now trying to solve a 100 Queens prob lem what you need to do is to open the problem xml file change the value at tribute in the lt chromosome_length gt select to 100 and change the value in the lt best_known_solution gt element to 4950 the total number of not on same diagonal constraint violation that can be removed is Worx 4950 and that s it The problem xml file after modification look likes the code listing 3 14 lt xml version 1 0 gt lt problem name 100 Queens_Problem gt lt overview gt lt chromosome_ length value 100 gt lt best_known_ solution existed true value 4950 gt lt maximization value true gt lt overview gt lt parameters gt lt parameters gt lt problem gt Listing 3 14 Cod
89. local search will be applied to the individual solutions in the offspring population 88 b Offspring Local Search Frequency is set to Medium local_ search_ frequency 0 5 but this Offspring Local Search Method is Disabled this parameter is not used c Offspring Local Search Sorting is set to None means the offspring population wont be sorted by fitness 7 Population Updating a Survival is set to Worst Replacement indicating only the least fit individual in the current population will be replaced by the best individual solution in the offspring population and this only happen if the least fit individual in the current population is not better than the best individual in the offspring population This strategy is known as the Steady State Replacement b Divergence is set to Disabled indicating that the population will not be re boiled when convergence occurs For the users who are familiar with the concept of Hybrid GA or Memetic Algo rithm the default Hybrid GA is not actually a Hybrid GA but a canonical Genetic algorithm with steady steady population replacement since local search is not used to improve the indivdiual solution in the populations 4 2 4 Use ADEP Statistics panel to view the currently se lected operators and parameter settings ADEP provides extra feature for the users to view all the current configuration select from ADEP menu Statistics Parameters and the Statistics dialog will appear as
90. m 2 problem representation in meta heuristic algorithms a candidate solution gen erated by the algorithm is usually represented in some form of symbols this is known as the problem s representation for example in the Travelling Salesman Problem TSP the TSP candidate solution solution is usually represented by an integer permutation in which each integer is unique and represent the city which the salesman travel in sequence this representation is the Integer Permutation representation 3 programming language any algorithm can be written in a number of high level programming language the programming language indicated in the title bar of Diagram Panel simply indicate to the user that the source code generated for the Hybrid GA would be in C cpp language The panel directly below the Command Panel is known as Algorithm Panel it is through the command in this panel that the user can switch between different algorithm frameworks as well as problem representation and the programming language of the generated source codes The panel directly below the Diagram Panel is the Functional Block Panel which display a tree representing various options available for a selected functional block of the algorithm framework as displayed in the Diagram Panel To the right of the Functional Block Panel is the Operator Node Panel which display the information pertaining to the information about the selected node in the tree control of the Functi
91. mark TestBench Directory Add File Delete File This project is created based on the lt cpp gt version of an algorithm in Integer Permutation representation Figure 4 1 The Create TestBench Dialog Create Benchmark Enter the name of the problem benchmark Figure 4 2 Create Benchmark dialog 67 Dialog Figure 4 3 The Benchmark Configuration Dialog 68 a benchmark is the particular problem setting for a problem instance When we cre ate the 100QueensBenchmark we are creating the problem setting for the problem instance 100 Queens Problem The information entered into the Benchmark Con figuration dialog is highly similar to what is being done to the problem xml file figure 4 4 shows the settings entered for the 100QueensBenchmark configuration dialog Overview Chromosome Length 100 Yes v 4950 Search Direction Maximization Best Known Solution Parameters Paramter List Parameter Name Parameter Value Parameter Type bool Update Remove Figure 4 4 Settings Entered for the 100QueensBenchmark configuration When settings are entered in the 100QueensBenchmark configuration dialog click OK button At this point the user is brought back to the Create Testbench dialog with the newly created 100QueensBenchmarks benchmark appear in the list box of the Benc
92. mber of conflict violation that can be removed is mization is set to true since we want the algorithm to search for a maximum objective value chromosome_ length is set to 8 which is the integer permutation length for a 8 Queens solution since the lt parameters gt section is not used in this case their dummy entries are removed The read nput in the case of 8 Queens problem does not require any modification 3 4 3 Understand _ evaluate method and How Objective Func tion Is Implemented in the Method After the modification done in the problem xml we can add in the objective function in to the Problem lt T gt _ evaluate method in the Problem h file Before we go into modifying the _ evaluate method let us try to understand the source codes generated in the _ evaluate by ADEP Below is the code listing generated by ADEP virtual double _ evaluate Individual lt T gt amp individual action 1 double objective value 0 0 Chromosome lt I gt pChrom individual 0 assert pChrom NULL Chromosome lt T gt amp chromosome pChrom assert chromosome empty faction 2 46 12 13 14 15 16 17 18 int chromosomeLength chromosome size assert chromosomeLength lt this gt get ChromosomeLength TODO add codes for fitness calculation here return objective value Listing 3 4 Code Listing for ADEP generated Problem lt T gt _ evaluate method In the code listing there is a
93. mented virtual double _ evaluate Individual lt I gt amp individual action 1 double objective_ value 0 0 Chromosome lt T gt pChrom individual 0 assert pChrom NULL Chromosome lt I gt amp chromosome pChrom assert chromosome empty action 2 int chromosomeLength chromosome size assert chromosomeLength lt this gt get ChromosomeLength TODO add codes for fitness calculation here for int i 0 i lt chromosomeLength 1 i for int j i 1 j lt chromosomeLength j int rowDif abs i j 48 22 int colDif abs chromosome i chromosome j 23 if rowDif colDif 24 25 objective_ value 1 0 26 27 28 29 30 return objective_value 31 Listing 3 5 Code Listing for modified Problen lt T gt _evaluate method with 8 Queens objective function implemented 3 4 4 Compile and Run the Modified Source Codes for 8 Queens Problem Now that we have completed the tasks of modifying problem xml and Problem lt T gt _ evaluate we can now run the algorithm to solve the 8 Queens Problem To do this compile the source codes using one of the following approaches 1 If you have VC 6 or VC 2005 installed in your computer you can just build the project using adep dsw VC 6 or adep sln VC 2005 the default build configuration for adep dsw and adep sln is set to Debug mode so if you are planning to use the executable for real time running test
94. mple linear regression 2 oa 0 62 a4 he he Rove CSRS w EEE 125 8 3 Samples Cyl sor s S43 2 a me eo Oe ae os Se we Soe Ss 126 8 4 Graph Plotter that reads and display the plot xml generated by Prob lema T gt interpret ae Ge bo He a ee OS A Eee Se ee 135 8 5 Algorithm Selection dialog showing Hybrid GA with floating string representation 146 List of Tables 3 1 8 Queens Arrangement in Chess Board 37 3 2 8 Queens Arrangement in Chess Board with Redefined Row and Column Symbols 54 oH Bock SH Be ew ee oc we Re OH Boe o ER GOH 37 3 3 Arrangement of 8 Queens using the solution provided by results xml 53 5 1 An integer permutation of length 10 105 5 2 A Binary string of length 10 4 06 ed025 6465 4 eee Sw were 4S 105 5 3 A Floating point string of length 3 2 44 106 8 1 Data Sample from a System sin 24 oe ve hoe ne eee See SSSA 120 8 2 binary string chromosome 2 224 ac das Ae ieeedade bees 122 8 3 chromosome section for Bo oe Re ee Ae we ee oe oe e 122 8 4 chromosome section for betay es oe a Oe a a a 122 8 5 floating string chromosome in Continuous Hybrid GA to represent Bo rere eT cTs er ereCerTe arenes ss 136 147
95. mutation or floating point string For example a TSP represented by integer permutation help remove a number of constraints on the problem and make the search much faster than binary string represented TSP Similarly for problem such as finding optimal parameters for curve fitting also known as linear and non linear regression problem floating point string may be a better choice for representation Although any of Hybrid GAs using different representations share similar work flow and framework the operators they use such as crossover mutation local search and so on are vastly different figure 5 5 show a comparison of the operator trees in the Offspring Muation functional block for Hybrid GA with integer permutation and binary string respectively Offspring Mutation g Offspring Mutation E Mutation Method B Mutation Method F Delete Insert F bit flipping F Inversion F Inversion F k Swap 4 Mutation Rate F Swap F low Mutation Rate F medium Integer GA binary GA Figure 5 5 Comparison between the Offspring Mutation operator trees for Hybrid GAs with Integer Permutation and Binary string representations respectively 106 In the following chapter some problems which are solved by Hybrid GA with binary and floating point strings as well as integer permutations will be discussed For now it is sufficent to know that all the algorithm in ADEP share the same algorithm framework d
96. n teger permutation has removed the first two constraints since the integer permutation automatically ensures that no two queens will be in the same row or same column then to determine quality of a solution is to determine how many not in same diagonal constraints violation are created or removed by the solution if the objective value is defined as the total number of not in same diagonal constraints violation are created the search will be minimization to minimize the total number of not in same diagonal constraints violation created if the objective value is defined as the total number of not in same diagonal constraints violations are removed by the solution the search will be maximization to maximize the total number of not in same diagonal constraints violations removed if we decide to use maximization search that is the objective value of a solution is defined as the total number of not in same diagonal constraints violation created by the solution we can define the objective function as follows N a con flict_removed i j 3 1 1 N z i 0 j i where 1 row row 4 Z row Z row 3 2 conflict _removed row row f 0 otherwise The equation defines a function con flict_removed i j which return 1 if the queen at row i and the queen at row j are not on the same diagonal and return 0 otherwise the statement row row 4 Z row Z row simply means that the Queen occupy
97. n 69 fitness 27 28 current generation 78 fitness 27 28 current generation 71 fitness 28 28 Press any key to continue Figure 3 11 Screen shot of adep exe running on 8 Queens Problem 50 Oo oo Ny na Fw NP FR ee A Ww N e O Figure shows that adep exe obtain the optimal solution for the 8 Queens Prob lem in the 71th generation of the Hybrid GA algorithm for user confused about what is a generation refer to section for a short tutorial on Hybrid GA 3 5 Obtain Solution from ADEP algorithm In figure the solution obtained by the Hybrid GA with integer permutation on 8 Queens is not shown So how can we obtain the information about the solution as generated by ADEP algorithm For the users who are wondering how to obtain the solution output from the ADEP algorithm there are several ways to obtain the solutions from ADEP algorithm that can be generated at different stage of the algorithm 3 5 1 Obtain Solution from results xml After the running of the adep exe as described in section 3 4 4 an XML file with the name results xml is generated in the root_ folder C1 This XML file contains many useful information about the algorithm The code listing 3 7 shows the content of the results xml as produced by the running of adep exe lt xml version 1 0 gt lt output simulation count 1 gt lt simulation index 1 gt lt generations gt lt gen generation 1 fitness 26 000000 time 0 000000 gt
98. n the problem solving environment and directly run a configured algorithm with that objective function without leaving the environment This feature might seen trivial in the first place but without this feature the task of test running algorithms for fine tuning and configuration can be daunting imagine that the user is adjusting a particular parameter for 10 different values without using this feature the user has to generate the code from the current configuration replace the default objective function with the problem specific objective function and then compile and run the source codes after that try to record the different performance statistics now that since the problem the user is trying to solve requires a lot of paramter tunning say that the user will have try to change around 20 different operators and parameters in order to obtain the desire configuration The repeated non brain involved process may finally kill the user s very creative brain cells or lead to the user having an enhanced vision of quiting his job On the other hand having this Run feature the user can just upload his objective function to the environment click the button Run which automatically compile the algorithm with the user s uploaded objective function and other information run the compiled algorithm and report the performance measures nicely in table format and chart figure which the user can then save all being done by only the clicking of Run b
99. ned by test running the default Hybrid GA algorithm this is the same settings as the Hybrid GA algorithm in chapter on 100 Queens Problem showed that the maximum objective value obtained is only 4920 This is smaller than the optimal 4950 that we are looking for suggesting that the current configuration of the Hybrid GA algorithm is not optimized to solve the N Queens Problem In this section we will show how to configure an algorithm using the ADEP GUI The next sections shows how one can configure a Hybrid GA using integer permutation representation to optimally solve the N Queens Problem Section 4 2 2 will illustrate how to access the code hint of those operators as well Just to refresh the users s memories about the Genetic Algorithm concept a short introduction of Genetic Al gorithm is presented below Section 4 2 1 followed by a description of the graphical 80 elements in the Functional Block Panel and Node Information Panel Section 4 2 2 and a discussion on the default settings for Hybrid GA Section 4 2 3 4 2 1 Basic concept of Hybrid Genetic Algorithm Hybrid GA Integer Permutation cpp Figure 4 13 Diagram Panel showing the workflow of a Hybrid GA Figure 4 13 shows the workflow of Hybrid GA in the Diagram Panel Notice that the Offspring Mutation functional block has a green color border on its two sides this indicates the Offspring Mutation functional block is the currently selcted functiona
100. nfiguration this is still not the optimal solution let us now select the operator node Offspring Local Search Local Search Method Two Genes Swap Step from the currently configured algorithm and to the test run again The Fitness VS Generation chart in figure 4 24 shows that this time the algorithm finds the global optimal solution with fitness 4950 in the 113 th generation The StatisticsInfo table in figure shows that it took 40 8 seconds for the newly configured algorithm to find the optimal solution Now restart ADEP and from the default configuration make the following changes 1 select Offspring Local Search Local Search Method Two Genes Swap DFL 2 select Offspring Local Search Local Search Frequency High And test run the 100 Queens Problem again figure shows that the optimal solution with fitness 4950 is obtained in 11th generation 95 Chart Fitness VS Generation Simulation 0 Fitness YS Generation Figure 4 24 Fitness VS Generation chart for test running 100 Queens after the Two Genes Swap Step is selected StatisticsInfo Simulation Run at Fri Jun 13 12 23 19 2008 Number of Simulation 1 avg CPU time ms 40813 00 min CPU time ms 40813 00 avg Generations 113 min Generations 113 avg Fitness 4950 000 best Fitness 4950 000 best known solution 4950 000 avg Gap 0 000 min Gap 40 000 Figure 4 25 Statistics Info table for test running 100 Queens Problem after Two Genes Sw
101. ng 8 9 modified Problem lt T gt interpret for floating point representation 141 Chapter 9 ADEP Example A Minimization Problem 142 List of Figures 1 1 ADEP Features A Highly Intuitive GU 12 2 1 ADEP Installer Screen Shot After Launch 20 2 2 Enter installer password i 2424 a0 e4G6e o ede GS a See G wwe ee 21 2 3 Select a directory to install ADEP 22 beh bee REA EE SE ERS RES 23 2 5 ADEP on Launchj oo de RA et eH oe Pew we 24 2 6 ADEP About Dialog Showing the Software is unlicenced 25 2 7 ADEP Registration Dialog oaa aaa 25 2 8 ADEP About Dialog Showing the Software is now Licenced 26 g amp l ADEP GUI padacie m mon coa pina BE pora Bia Roe SAnS E i 28 3 2 ADEP Command Panel 0242646648484 fe ee eee eee 29 3 3 ADEP Diagram Panel showing the default Hybrid GA framework wor NOVA 6 de BS Oo d oe BOS AGE HR EM OSS KG OSE ERS AE HG 29 3 4 ADEP Generate Source Code Dialog 31 3 5 ADEP Browse For a Folder aoaaa aaa 32 3 6 ADEP dialog showing Generate Source Code task completed 32 33 3 8 A 8 Queens Solution a ooa aa 6 6k See eee Pe ee ee 36 3 9 Visual C 6 workspace with Problem h file displayed 41 ds a as aTe a e ena ena 41 Eana be Pas 50 3 12 The table printed by output htm file generated by Problem lt T gt interpret 59 4 1 The Create TestBench Dialog 024
102. nitely need to one way to initialize the population but the selection of the operator node Random under Initialization method with blue icon is optional In a GA one do not need to use Random to initialize the population all the time 83 initialization can be done by using other methods To see what each of those operator is about activate the node that represents the operator in the Functional Block Panel by clicking at the node and the Node Information Panel to the right of the Functional Block Panel will automatically display the information of the represented operator As shown in figure the currently activated operator in the operator tree of Population Initialization is the node Random under the tree node Initialization Method the Node Information Panel automatically display the code hint related to the activated operator node Block Population Initialization E Population Initialization ll initialization Method i F Load Ei Random lll population Size 2 high Broww Z medium l Update Description Figure 4 15 Random Operator Node being selected in the Functional Block Panel Let us pay some attention to the code hint displayed in the Node Information Panel in figure The following is a short descriptions of the elements contained in the code hint in figure 4 14 1 Random is selected this line tell us that the current operator node Random is selected to
103. nt_ sample 61 SSE y y_bar x y y_bar 62 63 64 section _plot gt SetDoubleAttribute SSE SSE 65 66 doc SaveFile plot xml 133 67 68 Oo ON rn FCF Wd Fe eR a wo FF Listing 8 5 modified Problem lt T gt interpret Now recompile the source codes and run adep exe again and we would obtain a plot xml file whose content is shown in code list lt xml version 1 0 gt lt simple_linear_regression gt lt parameters beta0 2 774394 betal 0 022163 gt lt plot SSE 0 007135 gt lt sample x 10 000000 y 2 569000 y_bar 2 552764 gt lt sample x 20 000000 y 2 319000 y_bar 2 331134 gt lt sample x 31 000000 y 2 058000 y_bar 2 087340 gt lt sample x 40 000000 y 1 911000 y_bar 1 887873 gt lt sample x 50 000000 y 1 598000 y_bar 1 666243 gt lt sample x 100 000000 y 0 584000 y_bar 0 558092 gt lt plot gt lt simple_linear_regression gt Listing 8 6 The plot xml generated by Problem lt T gt interpret Figure illustrate a 2D graph plotting application that shows the ploting of simple linear regression together with the sample points by reading the content of plot xml generated by Problem lt T gt interpret 8 3 9 Configure Binary Hybrid GA to improve algorithm per formance Binary Hybrid GA can be configured through the ADEP GUI to improve the perfor mance of the algorithm for how to configure algori
104. ntains the source codes generated by ADEP the generated source codes are nicely separated into different modules that is folders according to their functions For examples the csv_ doc folder contains the C class file that can read in a specific Excel file of the comma separated values file format on the other hand tinyxml folder contains the C class files that can parse and write XML files 3 3 Understand 8 Queens Problem and How it can be solved as an optimization Problem Before we rush into modifying the source codes we need to understand the paradigm in problem solving for optimization problem To facilitate the understanding on how to solve optimization the 8 Queens optimization problem is taken as an example and illustrated in the subsequent sections 3 3 1 How to Solve an optimization problem effectively To learn the approach on how to solve an optimization problem follow the steps below 1 Understand the problem and its constraints refer to 3 3 2 34 2 Understand how to formulate the problem solution using a particular represen tation refer to 3 3 3 3 Understand how to define the objective function refer to 3 3 4 4 The rest of the steps is just to write the algorithm to solve the problem by making use of the objective function and the representation 3 3 2 What is The 8 Queens Problem and What are its con straints The eight queens puzzle is the problem of putting eight chess queens
105. ntations and with other programming language such as Java The Ex NQueensProblem project is built only for integer permutation representation and C language the project can work with other algorithm frameworks with integer permutation though refered to Section 5 1 The connection between the project and the representation language setting is automatically taken care of by ADEP based on the currently select representatin and language Remember the title bar of the Diagram Panel that reads Hybrid GA Integer Permutation cpp as discussed in section 3 1 1 To see the created project select menu Run TestBench Manager In the Test Bench Manager dialog that appear shown in figure 4 6 select the Ex NQueensProblem from the Available TestBenches list box When the Ex NQueensProblem is se lected in the list box the Benchmarks and the TestBench Directory section as well as the status bar at the bottom of the TestBench Manager dialog are au tomatically updated for the selected project the status bar reads The TestBench lt Ex_NQueensProblem gt is based on the cpp version of an algorithm in Integer Permutation representation 4 1 2 Howto Test Run a ADEP TestBench project With the Ex NQueensProblem TestBench project properly set up and the modified files uploaded it is ready to test run the 100 Queens problem to do this Click Run command in the Command Panel of ADEP In the Run dialog that appear shown in figure 4
106. nterpret method in the Problem lt T gt class To understand how this is done we need to analyze a bit of the ADEP generated algorithm class heirarchy The Problem lt T gt class declared in Problem h file is a class inherited from the class Problem_ Base lt T gt class declared in Problem_ Base h residing in the root_ folder problem folder any virtual method declared in Problem_Base lt T gt can therefore be overriden 59 Oo ON nt FB WH KF pmd 12 13 14 15 16 17 18 19 20 21 22 in Problem lt T gt class one of these virtual methods is the Problem_ Base lt T gt interpret method To override this method simply copying it into Problem lt T gt declaration in the Problem h file from the Problem_Base h file Now with the interpret method added into the Problem lt T gt class the code listing in the Problem h file with comments omitted and source codes in readInput and _ evaluate omitted for the Problem lt T gt will look something like the code listing 3 9 namespace ADEP template lt class T gt class Problem public Problem_Base lt T gt public virtual bool readInput const char filename virtual double _ evaluate Individual lt I gt amp individual virtual void interpret Individual lt I gt amp individual ie Listing 3 9 Code Listing for Problem lt T gt delcaration in Problem h file with the virtual method interpret added Once the interpret
107. oblem lt T gt evaluate This step is almost the same as that defined in section except the decoding process for Bo and Bi is not longer needed and therefore removed The modified source codes for Problem lt T gt _ evaluate is shown in the code list ing 8 8 It can be seen in 8 8 that inserted code become simpler to add and easier to understand compared with that of 8 4 virtual double _ evaluate Individual lt I gt amp individual 138 Oo ON rn oa A UN Owe nynnnn wd Ww WN N FBR BR RP RF KF Fe Oo ON Oo A wWwWwnNrFr DW HMDT WAN DT FP wWwonr double objective value 0 0 Chromosome lt T gt pChrom individual 0 assert pChrom NULL Chromosome lt I gt amp chromosome pChrom assert chromosome empty int chromosomeLength chromosome size assert chromosomeLength lt this gt get ChromosomeLength TODO add codes for fitness calculation here double beta0 chromosome 0 double betal chromosome 1 double SSE 0 for i 0 i lt m_samples GetRowCount i double x m_ samples GetValue i 0 double y m_ samples GetValue i 1 double y_bar beta0 betal x SSE y y_bar y y_bar objective _value sqrt SSE return objective value Listing 8 8 Modified Problem lt T gt _ evaluate for floating point representation 139 8 4 9 Override Problem _Base lt T gt interpret in Problem lt T gt This step is almost the same as that defined in sect
108. older To continue click Next If you would like to select a different folder click Browse C Program Files ADEP At least 395 3 MB of free disk space is required Figure 2 3 Select a directory to install ADEP 2 3 Select a Directory for Installation In the next screen 2 3 the user is asked to select a directory for installation the default is C Program Files ADEP Select the target directory or use the default installation directory and press Next At this point the installer begin to install the ADEP files to the selected directory as illustrated in figure In subsequent screens the users are asked the options to create desktop and quick launch short cuts After the user make his prefered selections and press Next the installation is completed 22 6 Setup ADEP Installing Please wait while Setup installs ADEP on your computer Figure 2 4 ADEP Installation in Progress 23 2 4 Enter Registration Serial Number After the installation is completed the user can launch the ADEP application from the Start menu The following figure is the screen shot of the ADEP on launch E Untitled ADEP Population Initialization Population Updating Offspring Local Search Offspring Evaluation A ial es Population Evaluation Local Search Stopping Condition Offspring Producer Offspring Mutation Algorithm Panel En gt Hybrid GA End Block Stopping Condi
109. olution i 57 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 outfile lt lt lt td gt Q lt td gt else i outfile lt lt lt td gt amp nbsp lt td gt outfile lt lt lt tr gt n outfile lt lt lt table gt n outfile lt lt lt body gt lt html gt n outfile close Listing 3 10 Code Listing for Problem lt T gt interpret method reimplemented The Code listing 3 10 is a very simple code that print out a table the represents a chess board with the queens placed in the table the letter Q using the arrangement specified by solution specified in Problem lt T gt interpret Now recompile ADEP source codes and the runs the compiled adep exe after it is done running you will find a HTML file output xml in the root_ folder the figure belows shows the HTML file when it is open 3 5 3 Obtain Solutions at Different Generations by Overriding Problem Base lt T gt record_individual in Problem lt T gt class For some of the users outputing the final best solution might not be the only informa tion that he needs he might also be looking for the trend on how the global best solution is evolved from the first generaton to the last generation That is the user might be looking for the global best solutions generated at each generation of the algorithm The overriden Problem lt T gt interpret method simply cannot fullfill this requirement
110. olution each of which is a random integer permutation Population Size is selected as low which set population_ size 20 2 Local Search a Local Search Method is set to Disabled indicating that no local search will be applied to the individual solutions in the population b Local Search Frequency is set to Medium local_search_frequency 0 5 but this Local Search Method is Disabled this parameter is not used c Local Search Sorting is set to None means the population wont be sorted by fitness 3 Stopping Condition a Termination i Stopping Criteria is set to Generation Limited indicating the algorithm will be terminated when certain number of generations is reached Op timal Reached is set to Terminate indicating that if the best known solution found in the past is available and if the algorithm already find that solution then terminate ii Stopping Parameters A Maximum Duration is set to Low max_duration_in_secs 120 this parameter is not used as Stopping Criteria is not set to Time_ Limited or Time_ Gen_ Limited B Mazimum Generation is set to Low max_generations 2000 in dicating the algorithm will terminate after 2000 generations C Maximum Stagnation is set to Low max_stagnation_count 300 this parameter is not used as Stopping Criteria is not set to Stag nation _ Gen_ Limited b Update Global Solution i Record Candidate Solutions is set to Disabled indicating the Problem lt T gt record_population
111. ome individual 0 int chromosomeLength chromosome size double beta0 0 double betal 0 int hl 0 int h2 chromosomeLength 2 int i 0 int hldp 9 double sign0 chromosome h1 1 1 1 for i 1 i lt h2 1 i int index hldp 1 i if chromosome i 1 beta0 pow 2 0 static cast lt double gt index beta0 sign0 int h2dp h2 9 double signl chromosome h2 1 1 1 for i h2 1 i lt chromosomeLength i 132 34 35 int index h2dp 1 i 36 if chromosome i 1 37 38 betal pow 2 0 static cast lt double gt index 39 40 41 betal x signl1 42 43 TiXmlElement element__parameters new TiXmlElement parameters 44 element_parameters gt SetDoubleAttribute beta0 beta0 45 element_parameters gt SetDoubleAttribute betal betal 46 doc_root gt LinkEndChild element_ parameters 47 48 TiXmlElement section_plot new TiXmlElement plot 49 doc_root gt LinkEndChild section_ plot 50 double SSE 0 51 for i 0 i lt m_samples GetRowCount i 52 4 53 double x m_samples GetValue i 0 54 double y m_ samples GetValue i 1 55 double y_bar beta0 betal x 56 TiXmlElement element sample new TiXmlElement sample 57 element _sample gt SetDoubleAttribute x x 58 element sample gt SetDoubleAttribute y y 59 element sample gt SetDoubleAttribute y_bar y_bar 60 section _ plot gt LinkEndChild eleme
112. on Rate to 0 2 5 Population Updating a Set Survival to mu lambda Selection this operator will combine the 60 individual solution in the current population with the 60 individual in the offspring population and pick the 60 most fit individuals from the 120 indi vidual as the population into the next generation To make changes suggested above we need to update the operator tree at each of those functional blocks Let us start with the Population Initialization Select the Pop ulation Initialization functional block in the Diagram Panel in the operator tree of the Functional Block Panel Select Population Initialization Population Size Medium branch by double clicking the Medium operator node or activate Medium operator node and click Update command under the Node Information Panel A Operator Node Configuration dialog will pop up as shown in figure At the bottom of the Operator Node Configuration dialog as shown in figure 4 18 is a radio button that reads Select This Node and is unselected proceed to select the radio button this will select the operator node Next select the line the in the list box this will enable the parameter population _ size to be reads pop displayed in the text fields below the list box as shown in figure 4 19 In the Value text fields of the dialog shown in figure 4 19 change the value of the population _ size from 50 to 60 and click the Close button on the Operator Node C
113. on an 8 x 8 chessboard such that none of them is able to capture any other using the standard chess queen s moves The queens must be placed in such a way that no two queens would be able to attack each other Thus a solution requires that no two queens share the same row column or diagonal The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n x n chessboard where solutions exist only for n 1 and n gt 4 figure 3 8 demonstrate one of the possible solution for 8 Queens Problem The puzzle was originally proposed in 1848 by the chess player Max Bezzel and appeared in the popular early 1990s computer game The 7th Guest The problem can be quite computationally expensive as there are 283 274 583 552 64x63x x58x57 8 possible arrangements but only 92 solutions Therefore it is computationally very expensive to use brute force computational technique This is exactly the type of problem where meta heuristic algorithm such as Hybrid GA can obtain high quality solution within relatively short period of time 3 3 3 How to Formulate 8 Queens Problem Solution as Integer Permutation Problem Before we go into the details of formulation we will try to explain what is a permutation for those users who do not have any background on combinatorial optimization In combinatorial optimization a permutation is usually understood to be a sequence containing each element from a finite set once and onl
114. onal Block Panel These features will be further explained in the chapter that discuss about how to configure the ADEP generated algorithm 3 1 2 Generate Source Codes To generate the source codes from ADEP click the Generate button in the Command Panel the Generate Source Code dialog appeared as shown in figure 3 4 In the Generate Source Codes dialog as shown in figure click the Browse button and the Browse for a folder dialog will pop up as shown in figure In the Browse for a folder dialog select or create a folder into which the generated source 30 Select the folder to store the generated source codes Compiler Option Borland C 5 5 Figure 3 4 ADEP Generate Source Code Dialog codes will be stored When it is done click the OK button to go back to Generate Source Codes dialog Next in the Compiler Options drop down list of the Generate Source Codes dialog select a compiler for which to generate the compilation scripts for the source codes When it is done click the OK button on the Generate Source Codes dialog and ADEP will begin to generate source codes and store them in the folder that the user specified earlier on in the Generate Source Codes dialog When ADEP completes the task a message dialog will appear to inform the user about the status as shown in figure This complete the process of code generation in ADEP Remember the settings displayed at the title bar of the Diagram Panel a
115. onfiguration dialog figure 4 20 shows that change in the operator tree in the Functional Panel after the operator node update above and figure 4 21 shows the change in the population _ size in the Node Information Panel One thing to take notice is that although we did not deselect Low under Population when Medium under Population is selected Low is automatically deselected ADEP makes sure that conflicting settings wont be selected at the same time 91 Dialog populatio int Figure 4 18 Operator Node Configuration dialog for the Medium operator node under Population Size operator node int population size int ee e Figure 4 19 Operator Node Configuration dialog with the parameter popula tion_ size selected in the list box 92 g A Population Initialization Initialization Method P Load Random c lll Population Size Z medium Figure 4 20 operator tree of Population Initialization after the update of Medium operator node Figure 4 21 population_ size is shown to change to 60 after the operator node update 93 The Stopping Condition Termination Stopping Parameters Maximum Gener ations Medium can be selected by double clicking the operator node and select the radio button Select This Node in the Operator Configuration dialog that pops up The Offspring Producer Parent Selection Mating Pool Size can be manipulated in the similar way as the above To select
116. ource_code_folder_name gt cppLib lt source_code_folder_name gt lt description gt A genetic algorithm or GA is a search technique used in computing to find exact or approximate solutions to optimization and search problems Genetic algorithms are categorized as global search heuristics Genetic algorithms are a particular class of evolutionary algore also known as evolutionary computation that use techniques inspired_by evolutionary biology such as inheritance mutation selection and crossover also called recombination Genetic algorithms find application in biogenetics computer science engineering economics chemistry manufacturing mathematics physics and other fields lt description gt lt functional_blocks gt lt functional_block id offspring Producer gt lt LVRP_node name 0ffspring Producer type root selected true gt lt LVRP_node name Crossover type property selected true gt lt LVRP_node name Crossover Met type property selected true gt lt LVRP_node name 1 Point type Vvariance selected false gt lt LVRP_node name 2 Point type variance selected true gt lt LVRP_node name Cyclex type variance selected false gt lt LVRP_node name LOx type variance selected false gt lt LVRP_node name PMX type Vvariance selected false gt lt LVRP_node name Uniform type variance selected false gt lt LVRP_node gt lt LVRP_node name Crossover Rate type property
117. owCount returns the number of rows which is the number of sam ple data points as well m_ samples GetValue i 0 return the double value for x in the first column i th row of the csv file m_ samples Get Value i 1 returns the double value for y in the second column i th row of the csv file Now compile the modified source codes and run the adep exe you should see the the objective value decreased with generation on the console 8 3 8 Override Problem _Base lt T gt interpret in Problem lt T gt To obtained the final value of Bo and By and store those values to be used the user can use one of the methods discussed in Section In this section we override Problem_ Base lt T gt interpret in Problem lt T gt to understand how to do this refer to Section 3 5 2 For our purpose we created an XML file to stored the value of Bo and Bi Code list ing shows the implemented Problem lt T gt interpret To write XML using C we make use of tinyxml which is already included in the source codes generated by ADEP To use tinyxml classes in Problem lt T gt class add include tinyxml tinyxml h below the other include statements in the Problem h file 131 virtual void interpret Individual lt I gt amp individual TiXmlDocument doc TiXmlElement doc_root new TiXmlElement simple_linear_regression doc LinkEndChild new TiXmlDeclaration 1 0 doc LinkEndChild doc_ root Chromosome lt T gt amp chromos
118. present Simple Least Squares Solution using Binary Sting 122 3 2 Define the Objective Function for Simple Linear Regression 124 8 3 3 Generate HGA with Binary Representation using ADEP 124 8 3 4 Create and Save sample data in Excell 124 8 3 5 Modify problem xml 2 60 22 4G a ee Rw eee ware eo 125 8 3 6 Modify Problem lt T gt readInput method in Problem h 126 8 3 7 Modify Problem lt T gt _evaluate 22 4 24 ees ae ee brs 129 8 3 8 Override Problem _Base lt T gt interpret in Problem lt T gt 131 8 3 9 Configure Binary Hybrid GA to improve algorithm performance 134 8 4 Simple Linear Regression using ADEP Generated algorithm with Con tinuous Solution Representation 22 8 40 136 8 4 1 Represent Simple Least Squares Solution using Floating Point re ee ee ee eee ee ee ee ee a E 136 ee 4 2 Define the Objective Function for Simple Linear Regression 136 bce amp Beale ee oe ae Se ee ee Be eS Se eS wee 137 8 4 4 Create and Save sample data in Excell 137 ae Sees tue oO hae ere ee e 137 8 4 6 Modify Problem lt T gt readInput method in Problem h 138 8 4 7 Modify UpperLowerBounds xml file 8 4 8 Modify Problem lt T gt evaluate 8 4 9 Override Problem _Base lt T gt interpret in Problen lt T gt 9 ADEP Example A Minimization Problem List of Figures List of Tables 143 147 C
119. problem xml This step is almost the same as that defined in section except the value attribute of the lt chromosome_length gt element is change to 2 137 ON aw KR ww 1 8 4 6 Modify Problem lt T gt readInput method in Problem h This step is the same as that defined in section 8 3 6 8 4 7 Modify UpperLowerBounds xml file The ADEP generated Continuous Hybrid GA relies on an XML file called Upper LowerBounds xml to provide the upper and lower bounds for Bo chromsoome 0 and 3 chromosome I respectively The default entries in the file is sufficient but the default range is extremely large which will cause the algorithm to converge slower therefore the user should enter the appropriate ranges for the chromosome genes in this file Code listing shows the modified content of UpperLowerBounds xml in the code listing lt gene gt element with index attribute being 0 contains the upper and lower bounds for Bo and lt gene gt element with index attribute equal to 1 contains the upper and lower bounds for Bi lt xml version 1 0 gt lt UpperLowerBounds gt lt default bounds upper_bound 1000 lower _bound 1000 gt lt individual_ gene _bounds gt lt gene index 0 upper_bound 1000 lower_bound 1000 gt lt gene index 1 upper_bound 0 lower_bound 2 gt lt individual_ gene_ bounds gt lt UpperLowerBounds gt Listing 8 7 The modified UpperLowerBounds xml file 8 4 8 Modify Pr
120. ration number fitness value at the generation as well as time from the start running time of adep exe in milliseconds 2 The lt solution gt section include the global best solution found by the algorithm until the last generation of the algorithm Therefore this is the solution that the 52 user is looking for the 8 Queens problem using the information in this section the arrangement of 8 queens on the chess board can be easily reconstructed by treating each lt gene gt elements in lt solution gt section as a queen and its index and value attributes as the row and column position that the queen occupies We can therefore reconstruct the 8 Queens solution as following table using the lt solution gt section Queens 0 1 2 3 4 5 6 7 row 0 1 2 3 4 5 6 7 col 4 1 3 6 2 7 51 0 Table 3 3 Arrangement of 8 Queens using the solution provided by results xml 3 The lt problem gt section basically record the information that is originally avail able in the problem xml in the root_ folder C1 except that it also records the exact time at which the algorithm is started The generation of results xml file is enabled by default in the algorithm it can also be disabled using the ADEP GUI which we will discuss later one of the benefits is that the ADEP generated algorithm is able to record multiple simulations a simulation is a run of adep exe Therefore if the adep exe is run twice then two lt
121. re the set of feasible solutions is discrete or can be reduced to a discrete one and the goal is to find the best possible solution Examples of combinato rial optimization include Quadratic Assignment Problem QAP Traveling Salesman Problem TSP Vehicle Routing Problem VRP Hamiltonian Cycle Problem HCP N Queens Problem Knapsack Problem and so on Numerical optimization is another branch of optimization Its domain is optimiza tion problems where the set of feasible solutions is continous or numerical values and the goal is to find the best possible set of numerical values Examples of numerical optimization include linear and nonlinear regression analysis and so on Each of those combinatorial and numerical problems can find numerous real life applications 1 2 2 What Are Meta heuristic Algorithms Many practical real world combinatorial and numerical optimization problems tend to be computationally intractable they usually belong to the category of NP hard problem implying they cannot be solved by exact method in tractable time period While advancement in computer technology is able to provide significant headway by making available immense computing horsepower it is far from being able to address the needs of solving complex optimization problems The challenge is really in the algorithms front Since traditional exact techniques such as branch and bound cannot solve those problems in tractable time heuristic algorithms were
122. rk section the Create Benchmark dialog appear which is illustrated in figure Entering a name say l00QueensBenchmark into the textbox of the Create Benchmark dialog and press OK This bring up a Benchmark Configuration dialog as shown in figure The Benchmark Configuration dialog in figure show very similar layout to the problem xml file contents refer to section 3 4 2 for the problem xml analysis The dialog also consists of overview and parameters section This brings up a question What is a benchmark which we have not answer up to this point Remember that in section the ADEP algorithm is designed to be highly flexible such that the algorithm is written to work with a problem but not with a problem instance To differentiate a problem and a problem instance N Queens Problem will be a problem but 100 Queens Problem is a problem instance what is contained inside the prob lem xml file is the problem instance setting 100 Queens Problem setting whereas the algorihtm itself can solve the N Queens problem remember to solve 100 Queens Problem in section the source codes does not require to be modified and recom piled at all and the TestBench project created represent the problem itself N Queens Problem Now Let us go back to answer the question of what is a benchmark 66 Create TestBench ogram Files ADEP Run Project Name Benchmarks Create New Benchmark Update Benchmark Delete Bench
123. s described in the generated source contains the configured algorithm of Hybrid GA written in C language and whose problem representation is in integer permutation 3 2 What are the C source codes generated In the section 3 1 2 ADEP generate and store the C source codes in the user specified root_ folder C1 The source codes contains the configured algorithm of Hybrid GA written in C language and whose problem representation is in integer permutation Now Let us take a look at what files have actually been generated Open the root_ folder C1 in which the generated source codes are stored Figure 31 Browse For Folder Select a folder for generated source codes Important All previous contents in the folder will by erased Desktop My Documents a My Computer J My Network Places a Recycle Bin a ci Figure 3 5 ADEP Browse For a Folder Source Codes are saved into C Documents and Settings Mianshun Desktop c 1 Figure 3 6 ADEP dialog showing Generate Source Code task completed 32 illustrate the files and folders contained inside root_ folder C1 algorithms console cv doc elements functors main operators problem E tinyxml utilities ES adep dsp Faden dsw Bladen sin EHadep vcproj gt compile bat i makefile problem xml Figure 3 7 The list of folders and files generated by ADEP in the root_ folder C1 We will now explain what those folders and files
124. s unlicenced Registration You have not registered ADEP ADEP will expire in 90 days Enter your copy of serial number in the text box below Figure 2 7 ADEP Registration Dialog 25 About ADEP DER Figure 2 8 ADEP About Dialog Showing the Software is now Licenced 26 Chapter 3 Generate and Compile ADEP Source Codes In this chapter you will learn 1 How to use ADEP to generate C source codes 2 What are the C source codes generated 3 Understand the process involved in solving an optimization problem 4 How to modify the generated C source codes to solve the optimization prob lem 5 How to obtain the solution output form the ADEP generated algorithm for use To allow you to have a better understanding of the last two topics we will show you an real life problem solving example using the generated code Section describe the 8 Queens problem which is a real life combinatorial problem the 8 Queens Problem 3 1 Howto Use ADEP to Generate C Source Codes Before we go into the tutorial on how to use ADEP to generate C source codes let us be familiarized with the ADEP GUI 27 3 1 1 Explain ADEP GUI Launch the ADEP application as shown in figure Pon Steuer Pesan leami aae Population Initialization Population Updating Offspring Local Search Offspring Evaluation A iat Go C Population Evaination Local Search Stopping Condition Offspring Producer Offspr
125. s within ADEP 5 1 1 Select Simulated Annealing algorithm Start the ADEP application and click the command that reads Hybrid GA in the Algorithm Panel which is below the Command Panel in the ADEP GUI The Al 100 Algorithm Selection Currently Configured Algorithm Language cpp Representation Integer Permutation Hybrid GA A genetic algorithm or GA is a search technique used in computing to find exact or approximate solutions to optimization and search problems Genetic algorithms are categorized as global search heuristics Genetic algorithms are a particular class of evolutionary algorithms also known as evolutionary computation that use Figure 5 1 Algorithm Selection dialog pop up after click the button in the Algorithm Panel gorithm Selection dialog appear as shown in figure In the Algorithm Selection dialog as shown in figure The Language drop down list display the currently use programming language is cpp C The Rep resentation drop down list display the currently used representation for problem so lution Below These two drop down lists are the algorithm drop down list that display Hybrid GA which is the currently used algorithm At the bottom of the Algorithm Selection dialog is a information panel that displays some brief description of the current algorithm Now in Algorithm Selection dialog with the Language and Representation unchanged select Simulat
126. se chromosome sections the maximum value will be a binary string of l 1 s this can be convert to a maximum decimal value Zmar 2 1 the minimum binary value will be a binary string of l 0 s this can be verted to a min imum decimal value of Zmin 0 we must then convert the decimal value z obtained by binary to decimal conversion to a value B which will be in the range of value to between Bo Let us try an example suppose that the binary string chromosome is Le ds ey 2 Pt 0 Table 8 2 binary string chromosome we divide the binary string into two chromosome section of length 4 as shown below o 1 Table 8 3 chromosome section for Bo J1 fo 1 0 Table 8 4 chromosome section for beta 122 Binary Decoding Method 1 In this method we translate the binary string in to decimal value z Bo 1 234 1 2 0 2 1 13 and the binary string in to decimal value z 1 1 23 0 2 1 2 0 10 The upper and lower bounds of z are Zmar 24 1 15 and Zmin 0 Assume that Bomas 5 and Lomin 0 Dimas 10 and Bi min 0 then s Poma Dome A 4 A 5 0 m m a 13 0 4 333 4 Dinas _ Binks 3 3 5 0 a a a 10 0 3 333 f Zmaz min 2 i Primin 15 0 j thus complete the translation from a single binary string chromosome to two floating point parameters Bo and Bi Binary Decoding Method 2 Another way to convert binary string to solution parameters is manu
127. shown in figure which shows the currently configured settings of the algorithm 4 2 5 How to Configure ADEP algorithm using the GUI Now we have understand the default configuration of the Hybrid GA in ADEP and we wish to make the following change from the default configuration 1 Population Initialization 89 Statistics Algorithm Name Hybrid GA Algorithm Id HGA Parameter List roperty sets a low poy ulation size Population Initialization gt Population a medium value of local search frequency ocal Search gt Local Search Frequency gt medium max_duration_in_secs determines the maximum duration before the algorithm cific number of generations Figure 4 17 Statistics dialog showing the currently configure algorithm a Set Population Size to Medium and set the population_ size parameter in Medium to 60 2 Stopping Condition a Termination i Stopping Parameters A Set Maximum Generations to Medium 3 Offspring Producer a Parent Selection i Set Mating Pool Size to High and set the parameter selected_ parent _ count in High to 60 therefore the offspring population size will also be 60 since two parents produce two children ii Set Parent Selection Method to Roullet Wheel 90 4 Offspring Mutation a Set the parameter mutation_range in k Swap under Mutation Method to 0 005 b Set the parameter mutation_ rate in High under Mutati
128. t between 0 and 1 known as Exploitation Bias if p lt Qo then p r s 1 s argmatues t r u n r u 5 1 0 otherwise else cae T T S ins 8 I r p r s ues r 7 r u n r u F j 5 2 0 otherwise end if In equation and T r u is the pheromone deposited on the arc from current state r to neighboring state u n r u is the heuristic cost from current 112 state r to u J r is the set of neighboring states from r that have not been visited by ant a is pheromone weight 3 is heustic cost weight Equation perform exploitation search in that the next state selected is a neighboring state s J r such that the product 7 r s n r s gt T r u n r u for all u J r Equation perform exploration search and is known as random proportional rule when ant finds the next state to move s it transits from r to s and perform a local pheromone update by T r s 1 p x r r s p x Ar r 8 5 3 Equation 5 3 is applied to the currently traversed arc r s so as to reduce the at tractiveness of r s to other ants T r s is reduced this encourage exploration p is between 0 and 1 Calculate cost in this functional block an objective value is calculated and assigned to each ant tour generated in Tour Construction Local Search Local search technique is applied to each ant tour optional and is not selected by default configuration Select Best Ant
129. the data points in table 8 2 1 Least Squares Method ei Yi Bo 2 is called the residual To find Bo and Bi the least squares method can be used In this method we are to find the values of Bo and By such that i N 1 i N 1 E yi bo Bixi 8 1 i 0 i 0 is minimized N is the number of data points sampled 120 8 2 2 Weighted Least Squares Method One of the common assumptions underlying linear and nonlinear least squares regres sion is that each data point provides equally precise information about the determin istic part of the total process variation In other words the standard deviation of the error term is constant over all values of the predictor or explanatory variables This assumption however clearly does not hold even approximately in every modeling application In situations like this when it may not be reasonable to assume that every observation should be treated equally weighted least squares can often be used to maximize the efficiency of parameter estimation This is done by attempting to give each data point its proper amount of influence over the parameter estimates A procedure that treats all of the data equally would give less precisely measured points more influence than they should have and would give highly precise points too little influence In weighted least squares method the objective is to find the values of Bo and Bi such that E D wie wilyi Bo F Brea 8 2 1 0 i 0
130. the tour sequency indicated by the solution For this type of objective value that stands for a cost the purpose of the meta heuristic is therefore to look for a solution that has minimum cost that is the objective of the meta heuristic algorithm is to look for a solution that has a minimum objective value as defined by the cost For some other problems the objective value can be defined as the gain for example In the Halmitonion Cycle Problem a solution is tour travelled by an agent such that each city is visited by the agent once and only once and the last cities reached by the agent is the first city that the agent left for the tour For this kind of problem the objective value of the solution is defined by the total number of cities that can be included in the Halmitonian cycle toured by the agent Then the problem becomes the search for a solution that has a maximum objective value as defined by the gain the total number of cities included in the Halmitonian cycle From the above analysis in optimization an objective function can be defined such that the search is for maximization or for minimization Therefore before we start to define the objective function for the 8 Queens Problem we need to decide whether the algorithm is a maximization or a minimization search 38 for the 8 Queens problem there are three constraints any two queens cannot be on the same row or same column or same diagonal the chromosome representation as i
131. thm through ADEP GUI refer to Section in particular the user should try the local search operators as those oper ators normally have a very dramatic effects on the solution quality and efficiency of the algorithm Note that the default binary Hybrid GA generated is actually canon ical GA without local search configured Further more the user may want to apply 134 FunctionApproximationErrorMinimization b 2 937433 10 00 19 00 28 00 37 00 46 00 55 00 6400 73 00 82 00 91 00 100 Linear Least Square Data Fitting Function Approximation Error Minimization Figure 8 4 Graph Plotter that reads and display the plot xml generated by Prob lem lt T gt interpret 135 Gray Code conversion in the Problem lt T gt _ evaluate method which is supposedly improve the quality of the algorithm solutions generated by binary Hybrid GA 8 4 Simple Linear Regression using ADEP Generated algorithm with Continuous Solution Representa tion In this section we introduce continuous Hybrid GA which is Hybrid GA using floating point string for solution representation For the users who have tried out the binary HGA above for the simple linear regression you will find the the floating point string for Continuous GA is a much more natural way to represent the parameters solution for the Simple Linear Regression Problem 8 4 1 Represent Simple Least Squares Solution using Floating Point String To use the floating str
132. tion Figure 1 1 ADEP Features A Highly Intuitive GUI As can be seen in figure a Memetic Algorithm or Hybrid Genetic Algorithm as it was previously known is represented as a flow chart that consists of blocks of function unit of the algorithm this represents the control of the algorithm when one of the block is selected in figure 1 1 the block Stopping Condition is selected the tree control below the algorithm flow chart displays the various options available in this functional block what are configurable The tree control display the various 12 operators that reside in the functional block and are organized into the tree structure to indicate their execution sequence and relationships the value and selection of those operators can be easily accessed or updated by double clicking the node that represent the operator In the Command Panel at the top right corner of the application GUI there are three buttons Generate to generate codes Run to run the configured algo rithm Learning to invoke the automatic configuration engine to learn the problem and configure the algorithm for the problem the caption of which indicate the three main functions of ADEP Below the Command Panel is the Algorithm Panel in which there is a button whose caption reads Hybrid GA indicating the current configuration is for a Hybrid Genetic Algorithm the bottom right panel next to the tree control
133. tion Foo P resu vaximum stagnations Bo g k F reima Figure 2 5 ADEP on Launch The full license of ADEP comes with a serial number without this serial number the full function of ADEP is only provided for the first 90 days After this period the user need to purchase the license in order to enjoy its function The current license of ADEP after its installation can be view in the About dialog by selecting the menu Help About The About dialog is shown in figure If the user already purchased the licence and has the serial number the serial number can be entered by selecting the menu Help Register After the menu selection the Register dialog appeared as seen in figure In the registration dialog the user can copy and paste the serial number in the text box and press OK If the serial number is entered correctly the user will be informed about the success of registration and the About dialog after registration is shown in figure 24 About ADEP You have not registered ADEP ADEP will expire in 90 days Your last time exiting ADEF is Tuesday June 10 2008 Warning this computer program is protected by patent right Unauthorized reproduction or distribution of this program or any portion of it may result in severe civil and criminal penalty and will be prosecuted to the maximum extent possible under the law Figure 2 6 ADEP About Dialog Showing the Software i
134. uld have no problem understand the various operators and how they can be changed for configuration 5 2 Understand Hybrid GA under different represen tations different optimization problem usually require different solution representation in order to be solved naturally and optimally Among the most common representations are binary string integer permutation and floating point string To Select Hybrid GA with a different representation click the button in the Algorithm Panel of ADEP GUI and select the representation from the Representation drop down list floating point string option is labeled Continuous in the drop down list If you have read through the previous chapters on the example of N Queens Prob lem you should be quite familiar with the integer permutation by now For those user who are not familiar with binary and floating point strings representations the following some some examples of the 3 representations 0 513 7 2 4 11 8 9 Table 5 1 An integer permutation of length 10 1 pE Ep E Table 5 2 A Binary string of length 10 2 3 105 0 345 7 23 8 8888 Table 5 3 A Floating point string of length 3 Binary string is most commonly used representation and prevalent in the theory of Genetic Algorithm Altough almost all the problems can be represented using binary strings some times it is more natural and efficient to represent a solution as an inte ger per
135. utton 15 1 3 7 ADEP can replace the task of looking for the best con figured algorithm on the problem as mentioned in 1 3 6 the process of configuring algorithm can be daunting even with the Run feature especially for a new problem for which approach to obtain the best configuration is unknown since the user cannot tell whether the configuration he obtained so far is good enough In such a situation the automatic configuration engine become extremely useful the process of preparing is also extremely easy and almost identical to that of the Run feature in the user upload the objective function then click Learn button on the Command Panel the automatic configuration engine is exported to a user specified folder and in there it is compiled and run No more user interaction is required the automatic configuration engine periodically look for promising configuration and save them to files the user can leave the configuration engine to run on its own and only come back later to collect the best configuration found by the engine those configuration files can then be converted back to source code by ADEP instead of performing a brute force searching for best configuration which will be next to impossible since the sheer number of possible configuration and the time taken to test run each configurable the automatic configuration engine makes use of meta heuristic machine learning algorithm to perform intelligent search for the best con
136. y once The concept of sequence 35 Figure 3 8 A 8 Queens Solution is distinct from that of a set in that the elements of a sequence appear in some order the sequence has a first element unless it is empty a second element unless its length is less than 2 and so on In contrast the elements in a set have no order 1 2 3 and 3 2 1 are different ways to denote the same set In the Hybrid GA source codes the values in integer permutation usually has a range with minimum value being 0 and maximum value being n 1 where n is the length of the permutation therefore some examples of an integer permutation of length 4 will be 0 1 2 3 3 1 2 O and 2 1 0 3 and so on the particular reason that it starts with zero is because in most of high level programming language an array usually start with 0 Now that you understand what is an integer permutation we will define some syntax for integer permutation here suppose an integer permutation x 5 3 4 2 1 0 then length x 6 is defined as the length of the permutation x and x 0 5 and x 2 4 indicate that the value at the 0 th index of x is 5 while the value at the 2 th index of x is 4 The 8 Queens problem solution can be easily represented by an integer permutation 36 we will demonstrate how to transform the solution displayed in figure 3 8 into an integer permutation below is a table showing the arrangement of quenes on the chessboard in figure Qu

ADEP User Manual ADEP 1.0 User Manual Compiled

Contents

Download Pdf Manuals

Related Search

Related Contents