What impact does the initial solution have in the case of non-linear optimization problems and (solved by) evolutionary algorithms?
For instance, initial solutions have an impact with linear programming.
Would it have any effect to rerun a non-linear optimization problem after a certain or good initial solution was found (and the evolutionary algorithm stopped)? Particularly/ for example in cases with many possible local solutions, or local solutions rather close to each other.
Would the latest known initial/ best solution affect something like solution space sampling or local solution sampling?
As recommended by Michael Patriksson, I also recommend that you attempt to solve (or get bounds for) at least small instances of your problem with mathematical programming algorithms such as COUENNE (https://projects.coin-or.org/Couenne) or other similar solvers. Beyond the insights on problem structure that you may learn in the process, this will also help to assess the solution quality of your metaheuristic on small datasets.
Now, regarding the impact of initial solutions in population-based search (e.g., genetic algorithms), you should have two general goals in mind: (1) diversity, (2) quality. For some problems, spending a lot of (coding and computational) effort to generate clever solutions is not worth it, as in a fraction of seconds your population-based algorithm may retrieve solutions of equally good or better quality. In such situations, ad-hoc construction techniques may even lead to reduce your population diversity without a clear benefit. For example, for some combinatorial optimization problems arising in transportation and logistics (vehicle routing problem), we had much more success with a randomized initial population subject to local search (equivalent to gradient descent in continuous space) as this would much better sample our search space. Moreover, diversity is important in the initial stages of the search as well as later on, and therefore should be actively preserved to avoid phenomenons of premature convergence.
It depends on several factors - the method, the starting point, the properties of the objective function as well as the definition of the constraints. The question is too wide and unclear to attempt an answer, because there isn't one. You need to be more precise.
Your descriptions yield questions of another kind: why do you not use methodologies from mathematical optimization? At least as a benchmark it would be interesting - as you have NO certificate of optimality in your methodology - whereas mathematical optimization include optimality certificates.
Hi, all depend on the kind if evolutionary algorithm you are using. In case of "population based" methods as PSO methods for example, the sensitivity to the starting points decreases with the size of the initial population I would say in a first analysis.
As recommended by Michael Patriksson, I also recommend that you attempt to solve (or get bounds for) at least small instances of your problem with mathematical programming algorithms such as COUENNE (https://projects.coin-or.org/Couenne) or other similar solvers. Beyond the insights on problem structure that you may learn in the process, this will also help to assess the solution quality of your metaheuristic on small datasets.
Now, regarding the impact of initial solutions in population-based search (e.g., genetic algorithms), you should have two general goals in mind: (1) diversity, (2) quality. For some problems, spending a lot of (coding and computational) effort to generate clever solutions is not worth it, as in a fraction of seconds your population-based algorithm may retrieve solutions of equally good or better quality. In such situations, ad-hoc construction techniques may even lead to reduce your population diversity without a clear benefit. For example, for some combinatorial optimization problems arising in transportation and logistics (vehicle routing problem), we had much more success with a randomized initial population subject to local search (equivalent to gradient descent in continuous space) as this would much better sample our search space. Moreover, diversity is important in the initial stages of the search as well as later on, and therefore should be actively preserved to avoid phenomenons of premature convergence.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics