There is not specific way to reach global minimum. One can fine tune the genetic parameters to achieve the optimal fitness function by setting the convergence criterion.

Two things. First there is no mathematical proof that in parctical, complex cases the GA converges to the global optimum(or minima). This can be proven only by tests: trying out your GA on several appropriate example problems. Other is,that GA can only approach the global optimum with appropriate preciseness (Just like the nature does). This is why GA is especially appropriate for use in Engineering problems, where no absolute preciseness is needed.

Okay, here is how I did it.

First create a basic GA, a GA that works (converges). To do this, first create the genetic representation of the problem - into this, include only those design variables that have the biggest influence on the problem (keep it simple). Next create the goal

(fitness) function using the created genetic representation. Here try to figure out, how will the fitness function represent the best the goal you want to achieve. Now finding the maxima or minima of this function is our goal. If, for example your problem is to minimize error, it is then minima finding. Important: Keep the function simple: calculation costs low. Apply simple math: addition, or average. The operators, other parameters of GA, take from literature.

To make sure GA works, experiment, try it out on severeal example problems that differ from each other singnificantly!. After these tests, due to robustness of GA, it is very likely that it gives result very close to the global optimum. Now you created the basic GA.

Hint: if you can, create such a fitness function where for example the optimum value is known (e.g. in case of error minimization, minima is zero, that  you  want to approach appropriately close).

Now comes tha hard part. Fine tuning,. Fine tuning means creating GA variants to test, and find the best. This is done by slight changing of GA parameters (population size and other parameters, operators, even fitness function). Change only one parameter at once, but try out several possible values! Re-run these GA variants on experimental problems, and accept that parameter value, at which the changed GA converges every time and it is reasonably quick. Accept this parameter's value as fixed, and continue to the next GA parameter, and so forth, to the last one

Try to fine tune the genetic representation, the fitness function first, but have in mind that complex genetic representation and fitness will SLOW down the algorithm.

Continue with population size, mutation, mutation ratio etc.

Put each GA variants' running results into chart, and evaluate them in the function of generations or time to run needed to find the best value.

You can prove your algorithms's effectiveness (fastness and reliability to achieve global optimum) by these charts.

I hope I helped you?

Essentially, GAs do not guarantee any global optima for all the types of functions. However they are able to provide efficient solutions for nonconvex and excessive nonlinear problems. If your objective function is convex, i suggest gradient based algorithms. Otherwise, you should try various configurations of GAs to reach efficient solutions as well as many runs.

we cannot glean any

proof of evidence that the optimal solution has indeed

been found. However, you can stop when any of the following two criteria

are met:

a. The pre-defined maximum affordable number of generations

Gmax has been exhausted.

b. Δgmax generations have been explored without a trial

vector being accepted, which also implies that Δgmax

generations have passed without any reduction of the

CF.

You can refer:

@article{zhang2012turbo,

title={Turbo multi-user detection for OFDM/SDMA systems relying on differential evolution aided iterative channel estimation},

author={Zhang, Jiankang and Chen, Sheng and Mu, Xiaomin and Hanzo, Lajos},

journal={IEEE Transactions on Communications},

volume={60},

number={6},

pages={1621--1633},

year={2012},

publisher={IEEE}

}

@article{zhang2014evolutionary,

title={Evolutionary-algorithm-assisted joint channel estimation and turbo multiuser detection/decoding for OFDM/SDMA},

author={Zhang, Jiankang and Chen, Sheng and Mu, Xiaomin and Hanzo, Lajos},

journal={IEEE Transactions on Vehicular Technology},

volume={63},

number={3},

pages={1204--1222},

year={2014},

publisher={IEEE}

}

for the stopping criteria.

Dear Yushazaziah Yunos,

This attached link may be helpful for you, Please visit 

https://www.youtube.com/watch?v=9zfeTw-uFCw&list=PLRqwX-V7Uu6bJM3VgzjNV5YxVxUwzALHV

If the optimal global solution is known (theoretically demonstrated) then you know when you get close to it. This approach is taken when you test new methods using  test functions with known solutions. If the global solution is not known (open problems) the idea is to beat the best known solution or at least to confirm it. In this case you can use 3 stop criteria: 1) The maximum number of generations (iterations) was attained; 2) No progress is obtained over a large number of consecutive generations (iterations); 3) The diameter of the population (swarm, agents, etc.) is very small (the population converged).

There is no mathematical proof and no gaurantee. Two methodologies can help

1. Try to execute GA on large number of problems for which optimal point is known and 

Observe the generations that your GA needs to reach that point.

The number of generations can be then utilized to reach near to optimal solutions for

Varied problems. 

2. You can consider convergence whenever no significant change in the fitness of aolutions can be acheived after executing some fixed number of evolutions.

One way to assess the optimality of the solution is by comparing it with the optimal solution obtained using a mathematical model or an analytical method.

Dear Professor Yunos,

this is an interesting question. My expertise lies more within the area of gradient descent in recurrent neural networks (implementing a supervised learning algorithm). Therefore I cannot guarantee you that the following solution will make a good approximation in genetic algorithms. Nevertheless, combining genetic algorithms with simulated annealing might help to approximate a good solution (though there is obviously no proof for finding the global minimum).

best wishes and kind regards,

Rainer

Depends on your problem. Either use maximum no of iterations or threshold value to exit the loop

Dear Professor Yunos,

just one more suggestion: what about applying the traveling salesman algorithm. Although this usually gives you a local minimum instead of a global minimum, you could apply it multiple times, i.e. letting many salesmen start from different origins and then apply the genetic algorithm to all the proposed solutions you get. This provides a wide space in the error landscape, because you have many different origins. This should let you find a minimum that is lower than all the other minima. There are several publications on genetic algorithms and the traveling salesman problem. If you type genetic algorithm and traveling salesman into your search engine or other literature databases, you will get several publications.

best wishes and kind regards,

Rainer

The following reference is probably of no use for genetic algorithms, but just an idea how the global minimum can be inferred when you deal with a supervised learning algorithm: in this case you might be able to use the inferred global minimum as a starting point and reverse-engineer the weights. As a result, you will finally have a set of input units and hidden units and your weights. It can be applied in supervised learning because the desired activation values of the output units are prespecified. Hence, the minimum delta for each output can be computed right from the start. Once you have that, the global minimum of error has been inferred. Because the training set is also known, you only need to engineer a set of weights and hidden unit activations that map the input onto the desired output:

Spiegel, R. (2007). Bayesian statistics as an alternative to gradient descent in sequence learning. International Journal of Emerging Technologies in Learning. Vol. 2, No. 3.

Please let me know in case you cannot access it.

best wishes and kind regards,

Rainer

Dear Professor Yunos,

Usually we don't know, that the GA reached the global extremal location. If the last e.g. 100 population didn't resulted in better extremal value, practically we can believe, that we are in the optimum, but it is not sure.

The more deatailed answer depends on the task and the function to be optimised. 

If the function is similar to that can be seen in the 4. figure having a narrow peak and we search for the maximum: 

(Source of the figures: http://deap.readthedocs.io/en/master/api/benchmarks.html)

then the success of the search depends on the location of the points of the starting population and the location of the generated new points. Your chance to find the global maximum depends on the number of generated points. If one of the points is generated on the surface of the peak, then the algorithm can go close to the global optimum.  You can imagine that if the peak has more narrow form than to generate a point on its side surface has less chance. So you need to apply more generation with mutations to improve your chance to find the peak and then get a point that is close to the top.

If the given task has similar form but it is not continuous, but discrete and it has only one extremal point, than your result depends on your fortune. In such case the genetic algorithm cannot give you the global extremal point usually. Instead you have to apply a systematic search that checks and compares every point.

Summarising the aboves: The chance to go very close to the global optima depends on the surface (the task) and the applied parameters of the GA, mainly the mutation parameters. If you are close to the global optima, in case of contimuous surface you may apply analityc methods to identify the exact point of the extremum, like derivation, automatically refined local search using climbing algorithm or something similar iterative algorithm where the precision can be set freely.

In case of discrete function if the GA reached a close location of the global optima you can apply a systematic checkink of every discrete points in the surroundings of the best point of GA.

Remark: Using GA is a technology that requires experiments for successful use.

In short: We don't.

Thanks a lot for the replies

Of course, you are very welcome. Thank you for this interesting question.

Yours sincerely,

Rainer

Many of us use 'ga' in Matlab with following function:

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub)

In one of my optimization problem I have,

nvars = 4

A = []

b = []

Aeq = []

beq = []

lb = -1e4*[1,1,1,1]

ub = 1e4*[1,1,1,1]

To verify correctness of the solution I changed the lb and ub with values achieved in the previous solution; and it give the correct answer.

Is the approach to verify solution is ok?

in evolutionary algorithm as GA, there is no way to confirm that the solution reach global minimum, but you can compare with other solution and judge its

It depends upon problem domain. If the desired solution is obtained or time limit has been exhausted it should exit or restart.

Thank you for all your comments and suggestions. It really helps me in understanding the GA better and give me ideas with my problem solution.

Hello everyone,

I'm using GA to solve my problem but once the optimization completed the optimal parameters are the min and max value of the boundary

in this case, what's the issue?

Finding global solutions is an intrinsic difficulty in optimization generally speaking even when you work with determinstic algorithms. Genetic algorithms are heuristic algorithms, there are no guarantees that the algorithm will converge to the global optimal solution, the uncertainty in reaching the global optimal solution is a function of the (structure of the algorithm) in fact in the structure of the class it belongs to in general, take care that there is a randomness element involved that you can't neglect. If you are clever you can ONLY improve the chances of hitting a good approximation to the desired solution .

Good thing about the genetic algorithm is that it does a good job exploring the feasible set. You can use a hybrid algorithm too if you want. In the case of the nonlinear continuous constrainted optimization problems there are some hybrid methods in the littérature, you can use them.

I would say - as a global optimum enthusiast - that I prefer KNOWING what I get - and the only one is by using global optimisation tools. I have been involved in a few such real projects in industry, and they all say that this is the only way to go, and one reason is that in these industries they hate to get second-best solutions - only proven optima will be accepted. You don't get that EVER if you use heuristics - meta or not.

It all depends upon the application that is under optimization. The expected domain of output is defined by the concerned. If that is attained the algorithm terminates. The other option is based on iterations. If the output remains constant after defined iterations we can terminate.

Sarabjeet Singh The fact that it is not making progress does NOT indicate that you have found an optimum - you may be in flatland, or worse: you may be at a really bad stationary point (i.e., a point with all partial derivatives of the objective functions are zero) that could the globally worst point in the feasible domain!!

As a person who is interested in both mathematical programming and heuristics, I think that the hybrid heuristic-gradient based algorithms may have a better chance to obtain global optima than heuristics. Especially in large scale problems, in which the heuristics will rarely reach the global optima. The hybridization may help to increase the computational efficiency by using the gradient information while having a good global search in the design domain.

Pooya Rostami

I will try it as soon as possible. Thanks for the answer

Dear Salah Djerouni

Very good! go ahead with that…

Also, please note that finding the proper algorithms to be hybridized and the identification of the best layout of the combination in a way that the proposed hybrid can be preeminent in comparison with the basic algorithms are the points that need more effort. Some of such hybrids are available in the state-of-the-art (in related journals such as “Applied Soft Computing”) but there are still many potentials. I also recommend testing your algorithms in the problems with high numbers of design variables.

Pooya Rostami : As long as the hybrid method is used, I venture to suggest that the output will not be optimal - or at least it will very rarely be optimal. The only way to find out is to also solve the problem instance to optimality, in order to have a chance to even talk about whether the heuristics "often yields near-optima". Do you agree?

Dear Prof. Michael Patriksson ,

I am agreeing that with using a hybrid method, again it will not be possible to mathematically prove the global optimality of the result. Generally, mathematical programming is the best, but as a research field, I think that developing hybrid evolutionary methods is much better than developing heuristics (which have already the same benefits and limitations).

I think that the hybridization of an evolutionary algorithm with a gradient-based method will improve the diversity of the search in the design domain. For example, the individuals can be updated with both vectors determined by swarm intelligence and gradient information. I think that this works better than standard evolutionary and gradient-based algorithms (if the mathematical proof of the result is not a matter).

Also, in some specific cases where the gradient information cannot be derived analytically (for example, vehicle crashworthiness topological design) the finite difference is the only way. Therefore, the inaccuracy of the finite-difference which is coupled with simulation noise will lead to unsuitable designs with mathematical programming (bifurcation/buckling may also cause a discontinuity in the objective). Also, the evolutionary approach cannot be solely used due to the inefficiency caused by high dimensions (and also surrogate modeling). I think that hybridization would be beneficial in such cases. I am so curious to know your opinion about it.

It cannot be said with certainty that the genetic algorithm has found the global minimum value. Only by testing the algorithm with analytical benchmark functions, you can find the algorithm is correct. In other cases, you should compare the results with the laboratory data, or find a way to make sure the answers are correct. for example find a way to predicts the order of magnitude of optimal points.

And the verdict thus is ... ? Perhaps you should try REAL global solvers, and see how it goes.

The GA itself will never give the proven global optimum, because it handles and checks finite number of points - states -, if the terminating condition finishes the algorithm and you suppose that the best point of global optima has been found, you always can imagine a not checked point that has better value.

Proving: crossing operation can explore only a closed by the extremal values region. Only mutation can reach any point of the space. But the number of points generated by mutation is finite. So there are remained, not checked points in the space that may have any value.

It is a general fact that discrete search methods can find the global optima only if all points in the search space have been checked (directly or indirectly, e.g. with exclusion). Continuous methods, using derivation and analitical expressions can find the global optimum.

Unless you are able to solve the same problem with an optimization method that guarantees an optimal solution, you will never know that you have reached a global minimum. It kind of defeats the purpose of using GA in the first place: if you can quickly solve it to optimality, why do you need to use GA? All you can say is that for smaller and easier instances, it converges to the global minimum (if you find out empirically that it does).

Looking at the fitness of the best-found solution so far can be a good sign, but totally if you have no idea of the global optimum, let to progress the optimisation until the rate of improvement is negligible.

Unless you know what the global optimal value is, you can never tell. Genetic algorithms are stochastic optimizers and rarely converge to absolute optimality. Your best bet moving forward is to compare your optimized value to the best-found so far in literature. You can then consider your solution to be the global optimum until (of course) better ones are produced.