TechnicalArticles
2008-01-06, 16:32
Optimization with MATLAB and the Genetic Algorithm and Direct Search Toolboxhttp://www.mathworks.com/company/newsletters/digest/images/download_scripts.gif (http://www.mathworks.com/programs/digest_offer/sept04/optimization.html)
by Dan Doherty ([email protected]), Mary Ann Freeman ([email protected]), and Rakesh Kumar ([email protected])
Engineers and scientists are constantly looking for approaches to find optimal solutions, perform tradeoff analysis, balance multiple design alternatives, and quickly incorporate optimization methods in their algorithms and models. One key to successfully solving many types of optimization problems is choosing the method that best suits the problem. The Optimization Toolbox (http://www.mathworks.com/products/optimization/) and the recently released Genetic Algorithm and Direct Search Toolbox (http://www.mathworks.com/products/gads/) together provide a diverse set of methods that solve a variety of optimization problems.
Traditional derivative-based optimization methods, like those found in the Optimization Toolbox, are fast and accurate for many types of optimization problems. These methods are designed to solve “smooth,” i.e., continuous and differentiable, minimization problems, as they use derivatives to determine the direction of descent. However, using derivatives is often ineffective when problems lack smoothness, for example, problems with discontinuous, nondifferentiable, or stochastic objective functions. For nonsmooth problems like these, methods such as the genetic algorithm or the more recently developed pattern search algorithm, both found in the Genetic Algorithm and Direct Search Toolbox, are effective alternatives.
This article discusses a nonsmooth minimization problem that is best solved using the algorithms in the Genetic Algorithm and Direct Search Toolbox. We use this toolbox and methods from the Optimization Toolbox to solve the problem using:
The genetic algorithm (http://www.mathworks.com/company/newsletters/digest/sept04/optimization.html#geneticalgo)
The genetic algorithm in conjunction with a derivative-based algorithm from the Optimization Toolbox (http://www.mathworks.com/company/newsletters/digest/sept04/optimization.html#derivative)
The pattern search algorithm (http://www.mathworks.com/company/newsletters/digest/sept04/optimization.html#pattern) A Sample Objective Function
To help visualize the problem and results, we have chosen a problem with only two variables, but the algorithms we explore are not limited to such small problems. The objective function is a piecewise continuous function, that is, it has smooth regions separated by discontinuities, with one exceptional region that is nondifferentiable almost everywhere. Additionally, as is often the case in optimization problems, this function is smooth in the region of the minimum. Our goal is to find the minimum of this objective function.
Figure 1 shows a plot of this objective function. The M-file that defines this surface is called nonSmoothFcn.m (http://www.mathworks.com/programs/digest_offer/sept04/optimization.html), and is available for download. The red dot represents the location of the exceptional region.
http://www.mathworks.com/company/newsletters/digest/sept04/images/plot_func_w.jpg (http://www.mathworks.com/company/newsletters/digest/sept04/images/plot_func_wl.jpg)
Figure 1. Click on image to see enlarged view.
Minimizing the Objective Function Using the Genetic Algorithm
As outlined, we will use the genetic algorithm, a method for solving optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of initial solutions. At each step, it selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population “evolves” toward an optimal solution.
The genetic algorithm does not use derivatives to detect descent in its minimization steps, and so it is a good choice for problems such as our nondifferentiable problem. Because of the nature of the search done by the genetic algorithm, it is also often very effective at finding a global minimum.
The Genetic Algorithm and Direct Search Toolbox enables you to run the genetic algorithm from the command line or from a GUI called the Genetic Algorithm Tool (Figure 2), which you can open by typing gatool at the MATLAB command prompt. You can set up your problem and customize the genetic algorithm within the GUI. We specify the following options within the Genetic Algorithm Tool:
Fitness function—the objective function that we want to optimize
Number of variables in our optimization
Plot function—custom function called gaplotbestfun.m (http://www.mathworks.com/programs/digest_offer/sept04/optimization.html) that plots the best function value in each generation versus iteration (or generation) number. This function is available for download.
Plot interval—the number of generations between consecutive calls to the plot functions
Initial population range—the range of the individuals in the initial population http://www.mathworks.com/company/newsletters/digest/sept04/images/gui_gads_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/gui_gads_wl.jpg)
Figure 2. Click on image to see enlarged view.
To run the genetic algorithm, click Start. Once the optimization finishes, you can see the algorithm results in the Status and results pane and the Final point pane. The final point is shown in magenta on the surface plot in Figure 3. Figure 4 shows the best fitness value in each generation.
http://www.mathworks.com/company/newsletters/digest/sept04/images/magenta_w.jpg (http://www.mathworks.com/company/newsletters/digest/sept04/images/magenta_wl.jpg)
Figure 3. Click on image to see enlarged view.
http://www.mathworks.com/company/newsletters/digest/sept04/images/fitness_value_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/fitness_value_wl.jpg)
Figure 4. Click on image to see enlarged view.
From the surface plot, we see that the genetic algorithm finds a point near the minimum despite the nondifferentiable objective function. If we run the problem from the command line, we achieve a similar result:
FitnessFcn = @nonSmoothFcn;
optGA = gaoptimset('PlotFcns', @gaplotbestfun, 'PlotInterval', 5, 'PopInitRange', [-5 ; 5]);
[Xga,Fga] = ga(FitnessFcn,2,optGA)
Xga =
-4.7220 0.0205
Fga =
13.0003
The results are summarized as follows:
Exact
solution Genetic algorithm results Genetic algorithm solution
– exact solution x(1) -4.712389 -4.7220 -0.0096 x(2) 0 0.0205 0.0205 Objfcn(x) 13 13.0003 0.0003
Using a Hybrid Function with the Genetic Algorithm
While the genetic algorithm can often find a point near a minimum within a reasonable time frame, it can sometimes take the algorithm quite a bit longer to find that minimum within some small tolerance. When an application requires such accuracy, we can use a hybrid function to seamlessly combine the genetic algorithm with more efficient methods from the Optimization Toolbox.
The hybrid function begins optimizing at the best point returned by the genetic algorithm. As our sample problem is smooth in the area around the minimum, we can choose the fminunc function from the Optimization Toolbox as our hybrid function. This function uses a fast derivative-based method, and is designed for unconstrained minimization problems.
Because fminunc can efficiently find the minimum in a smooth region, we can transition to this function once the genetic algorithm brings the solution into this region. Figure 4 shows that the genetic algorithm finds a solution near the minimum within the first 15 generations. For this reason, we can change the Stopping criteria within the Genetic Algorithm Tool so that the genetic algorithm runs for only 15 generations instead of the default value of 100. This is enough for the algorithm to bring the solution into the smooth region, at which point we can begin our iterations with fminunc.
You can customize a hybrid function with its own set of options. For this problem, we use fminunc with an output function, which is called after each algorithm iteration. Our output function, fminuncOut.m, plots the best function value at each iteration of the fminunc algorithm on the same plot as the iterations of the genetic algorithm. We specify the output function in the Options pane of the Hybrid function section of the Genetic Algorithm Tool by typing the following:
optimset('Outputfcn',@fminuncOut)
After we run the optimization, the Genetic Algorithm Tool and best fitness plot display the optimization results, as shown in Figure 5.
http://www.mathworks.com/company/newsletters/digest/sept04/images/results5a_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/results5a_wl.jpg) http://www.mathworks.com/company/newsletters/digest/sept04/images/results5b_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/results5b_wl.jpg) Figure 5. Click on images to see enlarged view.
The best fitness plot shows that the best function value further decreases during the fminunc iterations (red diamonds). The results are summarized as follows:
Exact
solution Genetic algorithm with fminunc hybrid function results Genetic algorithm with fminunc
– exact solution x(1) -4.712389 -4.712389 -7.29017E-12 x(2) 0 1.6E-7 1.6E-7 Objfcn(x) 13 13.000000 7.5E-14
Note that the hybrid function noticeably improves the accuracy of results compared to the genetic algorithm, and costs only a few iterations of the fminunc algorithm.
Minimizing the Objective Function Using the Pattern Search Algorithm
Pattern search is an attractive alternative to the genetic algorithm, as it is often computationally less expensive and can minimize the same types of functions. Additionally, the Genetic Algorithm and Direct Search Toolbox includes a pattern search method that can solve problems with linear constraints.
Pattern search operates by searching a set of points called a pattern, which expands or shrinks depending on whether any point within the pattern has a lower objective function value than the current point. The search stops after a minimum pattern size is reached. Like the genetic algorithm, the pattern search algorithm does not use derivatives to determine descent, and so it works well on nondifferentiable, stochastic, and discontinuous objective functions. Pattern search is also effective at finding a global minimum because of the nature of its search.
We can minimize our objective function using the pattern search algorithm either from the command line or from a GUI called the Pattern Search Tool. To open the GUI, type psearchtool at the MATLAB command prompt.
Type the objective function into the GUI and specify a starting point on the upper nondifferentiable portion of the surface at [2 -2]. For this example, we choose the Best function value plot option with a plot interval of 5 for viewing the results of our optimization. To run the pattern search algorithm, click Start (Figure 6).
http://www.mathworks.com/company/newsletters/digest/sept04/images/search_tool_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/searchtool_wl.jpg)
Figure 6. Click on image to see enlarged view.
http://www.mathworks.com/company/newsletters/digest/sept04/images/pattern_graph_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/pattern_graph_wl.gif)
Figure 7. Click on image to see enlarged view.
As Figure 7 shows, the results of the optimization show that the pattern search algorithm finds a minimum that is very close to the exact minimum for our objective function. These results are summarized as follows:
Exact
solution Pattern search results Pattern search – exact solution x(1) -4.712389 -4.712387 1.895E-06 x(2) 0 0 0 Objfcn(x) 13 13.000000 3.592E-12
Summary
This article explored the methods available in the Genetic Algorithm and Direct Search Toolbox. We saw that the genetic algorithm is an effective solver for nonsmooth problems. Additionally, we found that the genetic algorithm can be combined with other solvers, such as the fminunc algorithm in the Optimization Toolbox, to efficiently find a more accurate solution. We used both the GUI and the MATLAB command-line interface to invoke the genetic algorithm. After using the genetic algorithm, we explored the less well-known but very effective pattern search method on our sample problem via the pattern search GUI.
The optimization techniques available in the Genetic Algorithm and Direct Search Toolbox, sometimes in conjunction with the methods in the Optimization Toolbox, expand the scope of optimization problems that engineers and scientists can solve to include problems with discontinuous, nondifferentiable, or stochastic objective functions.
更多... (http://www.mathworks.com/company/newsletters/digest/sept04/optimization.html)
by Dan Doherty ([email protected]), Mary Ann Freeman ([email protected]), and Rakesh Kumar ([email protected])
Engineers and scientists are constantly looking for approaches to find optimal solutions, perform tradeoff analysis, balance multiple design alternatives, and quickly incorporate optimization methods in their algorithms and models. One key to successfully solving many types of optimization problems is choosing the method that best suits the problem. The Optimization Toolbox (http://www.mathworks.com/products/optimization/) and the recently released Genetic Algorithm and Direct Search Toolbox (http://www.mathworks.com/products/gads/) together provide a diverse set of methods that solve a variety of optimization problems.
Traditional derivative-based optimization methods, like those found in the Optimization Toolbox, are fast and accurate for many types of optimization problems. These methods are designed to solve “smooth,” i.e., continuous and differentiable, minimization problems, as they use derivatives to determine the direction of descent. However, using derivatives is often ineffective when problems lack smoothness, for example, problems with discontinuous, nondifferentiable, or stochastic objective functions. For nonsmooth problems like these, methods such as the genetic algorithm or the more recently developed pattern search algorithm, both found in the Genetic Algorithm and Direct Search Toolbox, are effective alternatives.
This article discusses a nonsmooth minimization problem that is best solved using the algorithms in the Genetic Algorithm and Direct Search Toolbox. We use this toolbox and methods from the Optimization Toolbox to solve the problem using:
The genetic algorithm (http://www.mathworks.com/company/newsletters/digest/sept04/optimization.html#geneticalgo)
The genetic algorithm in conjunction with a derivative-based algorithm from the Optimization Toolbox (http://www.mathworks.com/company/newsletters/digest/sept04/optimization.html#derivative)
The pattern search algorithm (http://www.mathworks.com/company/newsletters/digest/sept04/optimization.html#pattern) A Sample Objective Function
To help visualize the problem and results, we have chosen a problem with only two variables, but the algorithms we explore are not limited to such small problems. The objective function is a piecewise continuous function, that is, it has smooth regions separated by discontinuities, with one exceptional region that is nondifferentiable almost everywhere. Additionally, as is often the case in optimization problems, this function is smooth in the region of the minimum. Our goal is to find the minimum of this objective function.
Figure 1 shows a plot of this objective function. The M-file that defines this surface is called nonSmoothFcn.m (http://www.mathworks.com/programs/digest_offer/sept04/optimization.html), and is available for download. The red dot represents the location of the exceptional region.
http://www.mathworks.com/company/newsletters/digest/sept04/images/plot_func_w.jpg (http://www.mathworks.com/company/newsletters/digest/sept04/images/plot_func_wl.jpg)
Figure 1. Click on image to see enlarged view.
Minimizing the Objective Function Using the Genetic Algorithm
As outlined, we will use the genetic algorithm, a method for solving optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of initial solutions. At each step, it selects individuals at random from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population “evolves” toward an optimal solution.
The genetic algorithm does not use derivatives to detect descent in its minimization steps, and so it is a good choice for problems such as our nondifferentiable problem. Because of the nature of the search done by the genetic algorithm, it is also often very effective at finding a global minimum.
The Genetic Algorithm and Direct Search Toolbox enables you to run the genetic algorithm from the command line or from a GUI called the Genetic Algorithm Tool (Figure 2), which you can open by typing gatool at the MATLAB command prompt. You can set up your problem and customize the genetic algorithm within the GUI. We specify the following options within the Genetic Algorithm Tool:
Fitness function—the objective function that we want to optimize
Number of variables in our optimization
Plot function—custom function called gaplotbestfun.m (http://www.mathworks.com/programs/digest_offer/sept04/optimization.html) that plots the best function value in each generation versus iteration (or generation) number. This function is available for download.
Plot interval—the number of generations between consecutive calls to the plot functions
Initial population range—the range of the individuals in the initial population http://www.mathworks.com/company/newsletters/digest/sept04/images/gui_gads_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/gui_gads_wl.jpg)
Figure 2. Click on image to see enlarged view.
To run the genetic algorithm, click Start. Once the optimization finishes, you can see the algorithm results in the Status and results pane and the Final point pane. The final point is shown in magenta on the surface plot in Figure 3. Figure 4 shows the best fitness value in each generation.
http://www.mathworks.com/company/newsletters/digest/sept04/images/magenta_w.jpg (http://www.mathworks.com/company/newsletters/digest/sept04/images/magenta_wl.jpg)
Figure 3. Click on image to see enlarged view.
http://www.mathworks.com/company/newsletters/digest/sept04/images/fitness_value_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/fitness_value_wl.jpg)
Figure 4. Click on image to see enlarged view.
From the surface plot, we see that the genetic algorithm finds a point near the minimum despite the nondifferentiable objective function. If we run the problem from the command line, we achieve a similar result:
FitnessFcn = @nonSmoothFcn;
optGA = gaoptimset('PlotFcns', @gaplotbestfun, 'PlotInterval', 5, 'PopInitRange', [-5 ; 5]);
[Xga,Fga] = ga(FitnessFcn,2,optGA)
Xga =
-4.7220 0.0205
Fga =
13.0003
The results are summarized as follows:
Exact
solution Genetic algorithm results Genetic algorithm solution
– exact solution x(1) -4.712389 -4.7220 -0.0096 x(2) 0 0.0205 0.0205 Objfcn(x) 13 13.0003 0.0003
Using a Hybrid Function with the Genetic Algorithm
While the genetic algorithm can often find a point near a minimum within a reasonable time frame, it can sometimes take the algorithm quite a bit longer to find that minimum within some small tolerance. When an application requires such accuracy, we can use a hybrid function to seamlessly combine the genetic algorithm with more efficient methods from the Optimization Toolbox.
The hybrid function begins optimizing at the best point returned by the genetic algorithm. As our sample problem is smooth in the area around the minimum, we can choose the fminunc function from the Optimization Toolbox as our hybrid function. This function uses a fast derivative-based method, and is designed for unconstrained minimization problems.
Because fminunc can efficiently find the minimum in a smooth region, we can transition to this function once the genetic algorithm brings the solution into this region. Figure 4 shows that the genetic algorithm finds a solution near the minimum within the first 15 generations. For this reason, we can change the Stopping criteria within the Genetic Algorithm Tool so that the genetic algorithm runs for only 15 generations instead of the default value of 100. This is enough for the algorithm to bring the solution into the smooth region, at which point we can begin our iterations with fminunc.
You can customize a hybrid function with its own set of options. For this problem, we use fminunc with an output function, which is called after each algorithm iteration. Our output function, fminuncOut.m, plots the best function value at each iteration of the fminunc algorithm on the same plot as the iterations of the genetic algorithm. We specify the output function in the Options pane of the Hybrid function section of the Genetic Algorithm Tool by typing the following:
optimset('Outputfcn',@fminuncOut)
After we run the optimization, the Genetic Algorithm Tool and best fitness plot display the optimization results, as shown in Figure 5.
http://www.mathworks.com/company/newsletters/digest/sept04/images/results5a_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/results5a_wl.jpg) http://www.mathworks.com/company/newsletters/digest/sept04/images/results5b_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/results5b_wl.jpg) Figure 5. Click on images to see enlarged view.
The best fitness plot shows that the best function value further decreases during the fminunc iterations (red diamonds). The results are summarized as follows:
Exact
solution Genetic algorithm with fminunc hybrid function results Genetic algorithm with fminunc
– exact solution x(1) -4.712389 -4.712389 -7.29017E-12 x(2) 0 1.6E-7 1.6E-7 Objfcn(x) 13 13.000000 7.5E-14
Note that the hybrid function noticeably improves the accuracy of results compared to the genetic algorithm, and costs only a few iterations of the fminunc algorithm.
Minimizing the Objective Function Using the Pattern Search Algorithm
Pattern search is an attractive alternative to the genetic algorithm, as it is often computationally less expensive and can minimize the same types of functions. Additionally, the Genetic Algorithm and Direct Search Toolbox includes a pattern search method that can solve problems with linear constraints.
Pattern search operates by searching a set of points called a pattern, which expands or shrinks depending on whether any point within the pattern has a lower objective function value than the current point. The search stops after a minimum pattern size is reached. Like the genetic algorithm, the pattern search algorithm does not use derivatives to determine descent, and so it works well on nondifferentiable, stochastic, and discontinuous objective functions. Pattern search is also effective at finding a global minimum because of the nature of its search.
We can minimize our objective function using the pattern search algorithm either from the command line or from a GUI called the Pattern Search Tool. To open the GUI, type psearchtool at the MATLAB command prompt.
Type the objective function into the GUI and specify a starting point on the upper nondifferentiable portion of the surface at [2 -2]. For this example, we choose the Best function value plot option with a plot interval of 5 for viewing the results of our optimization. To run the pattern search algorithm, click Start (Figure 6).
http://www.mathworks.com/company/newsletters/digest/sept04/images/search_tool_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/searchtool_wl.jpg)
Figure 6. Click on image to see enlarged view.
http://www.mathworks.com/company/newsletters/digest/sept04/images/pattern_graph_w.gif (http://www.mathworks.com/company/newsletters/digest/sept04/images/pattern_graph_wl.gif)
Figure 7. Click on image to see enlarged view.
As Figure 7 shows, the results of the optimization show that the pattern search algorithm finds a minimum that is very close to the exact minimum for our objective function. These results are summarized as follows:
Exact
solution Pattern search results Pattern search – exact solution x(1) -4.712389 -4.712387 1.895E-06 x(2) 0 0 0 Objfcn(x) 13 13.000000 3.592E-12
Summary
This article explored the methods available in the Genetic Algorithm and Direct Search Toolbox. We saw that the genetic algorithm is an effective solver for nonsmooth problems. Additionally, we found that the genetic algorithm can be combined with other solvers, such as the fminunc algorithm in the Optimization Toolbox, to efficiently find a more accurate solution. We used both the GUI and the MATLAB command-line interface to invoke the genetic algorithm. After using the genetic algorithm, we explored the less well-known but very effective pattern search method on our sample problem via the pattern search GUI.
The optimization techniques available in the Genetic Algorithm and Direct Search Toolbox, sometimes in conjunction with the methods in the Optimization Toolbox, expand the scope of optimization problems that engineers and scientists can solve to include problems with discontinuous, nondifferentiable, or stochastic objective functions.
更多... (http://www.mathworks.com/company/newsletters/digest/sept04/optimization.html)