There are many method to convert constraint optimization problem to non-constraint one .

Best methods are penalized methods to address constraints.

Best of luck. 

Fuzzy logic , NNT or similar algorithm are better performer but difficult to implement  

I am really grateful for your prompt answers.

You are absolutely right but I have read some papers about solving constrained optimization problems using pure meta-heuristic such as GA and PSO (Mathematical Programming). My question is how their authors have converted the constrained problem into an unconstrained one.

Some authors use Penalty Factors but I think there is another confusing matter in this method!

Because if I add the constraints into the objective function using Penalty Factors, how I can assign a correct value for these factors. I mean, can it be able to guarantee the optimal solution when the values of penalties are chosen very high or not?

Briefly, is the penalty factor method good or not? if so, can I find the right (optimum) values of penalty factors?

Regards,

Morteza Shabanzadeh

You have encoutered a rather common problem so I am sure that are several publications addressing the issue and suggesting ways to tackle it. Engineering problems have often interesting solutions right close to constraints.

One possible way is to use penalty factors as you have suggested. The penalty is usually expressed as a factor "w" multiplying the value of the constraint, this member is added to the actual objective function. The problem is that the larger is the weight of the constraint the more will the algorithm focus to minimize this penalty but avoiding dealing with the optimization of the actual objective resulting in a large set of feasible solution but suboptimal. The opposite can cause some unfeasible solutions to persist longer during the optimization. In both cases care must be taken and the only approach that I have tried is to try several weights and look in detail at the progression of the optimization to understand the best value of the weight. Usually, it is easier to start with low penalties and increase the penalty while being progressively more confident with the feasibility region.

With EA, another option is to impose that only individuals verifying the constraints are retained during the new generation and new individuals are generated untill the desired number of feasible individuals are obtained. Something similar is available in the Matlab GA tool.

Another very rough option is to generate enough large set of solutions, provided that there are equally well distributed (sub)optimal solutions, and sort out the feasible solutions after the optimazion has stopped. Unfortunately this is difficult for equality constraints, while it is easier for inequality constraints.

As always different optimization problems may be tackled in different ways so the different approaches may perform differently depending of the specific shape of the objective function and of the search space.

regards

/Matteo

Dear Morteza,

Strictly speaking, you don't have the guarantee that you will find the exact optimal solution of a constrained NLP by converting it into an unconstrained optimization problem with penalty functions. What is proven is that the solution of the penalty problem can be made arbitrarily close to the solution of the constrained problem when the penalty factor grows sufficiently large. (You have the same conclusions with interior point methods, when the barrier factor goes to 0). So the only "optimal" values for the penalty factors are when they go infinite. Meanwhile, the use of metaheuristics methods don't guarantee also the finding of the global solution in that convergence in finite time can not be generally proven. 

This does not mean that these approaches do not work well (independently or combined). It just means that you cannot use two "approximate" methods and expect them to give you strict guarantees of the finding of the global optimal solution.

So typically, you could imagine starting by initializing the penalty problem with very large penalty terms. This will lead you to a feasible point for sure (since the term corresponding to the constraint in the cost is dominant). But this point can be relatively far from the real solution and you can also have numerical issues (ill-conditioning or round-off errors e.g., although metaheuristics will perhaps be less affected than classical deterministic gradient-based methods).

Thus people generally use an approach called "Sequentiel unconstrained minimization", whereby a sequence of increasing penalty factors is generated starting from a relatively small value. Since when this value is small, the real original constraints will probably be not satisfied, these term need hence to be increased and the penalty problem repeatedly solved (with increasing values of the parameters) until the iterate respect all the constraints (to a termination criterion).

edit: it looks that Matteo and me provided a similar answer simultaneously :)

Dear Morteza Shabanzadeh,

meta-heuristic algorithms are based on random nature and optimum controlling parameter can be found.

But this method is based on error and trial.  

So you need to consider various penalty factors. Also this penalty methods may not perform similar for all categories 

Penalization is a straightforward method that restricts the selection procedure automatically. Extraneous checking for each individual with separate validation function may be time costly.

You can add a penalisation factor in the fitness function in such a way that it tends to the worst possible value went the constraint is not fulfilled (i.e. using a logarithm function).

Another way to deal with constraints could be checking them when a solution is created and assigning automatically a very bad fitness value if the constraint is not satisfied

A simple way is to take into account the constraints in the evaluation of the cromosomes in GA or particles in PSO, according to the number of not fulfilled constraints the value of  the fitness function is decreased. Here you could introduce weights for the constraints or using a fuzzy approach.

Static and dynamic penalty both can be considered, In my view dynamic penalty proves better convergence rate.

Hence,I like to prefer dynamic penalty 

Also Fuzzy logic is a good option,  

Dear Ghanshyam,

Would you please elaborate the method in which Dynamic Penalty is used? I am not familiar with this method you mentioned.

Do you mean the methods such as Subgradient Lagrangian Relaxation?

Regards,

Morteza Shabanzadeh

Dear Morteza, this paper may help. see the attachement.

PENALTY FUNCTION METHODS FOR CONSTRAINED OPTIMIZATION WITH GENETIC ALGORITHMS 

you can use penalty functions ...

In proposal of Akbari Reza, the number 2 (2- Working in a feasible search space where the individuals in the population are forced to satisfy the constraints.) may be no useful because in constraint problems usually the purpose of the search is finding feasible solutions.

Dear Matteo, Ghanshyam, Ashkan, Mojtaba, Reza, and Dr. Rafael,

I am really grateful to all of you for your noteworthy comments.

Regards,

Morteza

For Evolutionary Algorithms at least, there are four main strategies.

1) Specialized crossover and mutation operators that only produce valid solutions. This is probably the "normal" approach.

2) Penalty points that reduce the fitness of invalid solutions (including the "death penalty" that assign an infinitely strong penalty).

3) The Pareto-optimal approach that treats fitness and validity as independent metrics, allowing selection to focus on fit & valid solutions.

4) Introducing Genetic Repair operators, that convert invalid solutions into valid ones. Sometimes (but not always) solutions can be converted to make them valid. (for example by comparison against a known solution "template" or by "bounce-back" if a values exceeds a valid range).

Rewards for good behaviour will provide the necessary feedback to identify good solutions. 

Patricia

I just want to clarify the description of the penalty method in my first comment. I wrote that this consists in multiplying the weight "w" by the constraint. This is only one of the possible way to add a constraint to the actual objective function which may keep some linearities in the objective function definition. Indeed, since heuristic methods are often used to address highly non-linear problem with discontinuous search space, linearity is not really an issue. Accordingly any kind of function can be used to add a penalty (that is n-degree polynomials, exponential, etc.). If a constraint is considered as a boundary in the objective function space, it is often convenient (for the issues previously highlighted) to adopt a penalty that "smooths out" the boundary so that infeasible solutions close to the boundary are less penalized than solutions far away in the infeasible space. So ultimately the way to express the penalty generally depends on the shape of the constraint (which does not necessarily need to be linear). Indeed linear penalty functions may act as hard corners (the extreme case being a large constant offset of the objective function) where algorithms "bounce" so my little experience suggests that is better to have non-linear (although monotonous) penalty functions. I wonder if this is the "dynamic penalty" suggested by Ashkan Meamri, unfortunately I have no time to read his interesting paper.

Any optimization problem can be converted from matrix of inequality constraints Ax < B into a matrix of equality constraints Ax + s = B where s is known as a vector of "slack variables" that also have to be determined.  If you then transfer all independent variables to the right hand side and transform your matrix into upper triangular, you can combine generation of solutions such that independent variables on the right hand side are determined using real number GA operators with upper and lower bounds, while the dependent variables have been solved using Gaussian algorithm.  To see how this can be done, check my paper on using GA approach for solving non-linear transportation problems published in the Journal of Heuristics, Vol 6 (2), 2000, there are some useful ideas on how to always guess solutions that are feasible (I called this "gene therapy" approach).  The computational effort compared to guessing infeasible solutions and using large penalties to eliminate them was reduced by several orders of magnitude!  Also, the use of penalties to eliminate infeasible solutions seems to bias the search direction for heavily constrained problems, making it more difficult to find high quality local optimums.

Hi Morteza, I am new to participating in the Q & A. I hope I  have understood your question appropriately and that is that you are asking about "good" methods of constraint handling? If I have got tthe gist of your question, then this is perfect because I am very interested in this topic myself.

I put "good" in  quotation marks above because I am convinced that what is judged to be good is problem dependent, unfortunately/. To me, this is just a manifestation of Wolpert and MacReady's No Free Lunch theorem.

For a recent overview see: Mallipeddi et al (2010): Ensemble of Constraint HandlingTechniques in IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 14 (4).

There are of course a number of other reviews of constrained optimisation techniques available in the literature. Prof  Carlos Coello-Coello's repository found on the web at:http://www.cs.cinvestav.mx/~constraint/index.html is a useful starting point.

Recognising that the definition of "good" method might be problem specific, I give a brief summary of what I have, for my problem setting investigated, found to be efficient. Note that these algorithms can be used with population based stochastic heuristics (like GA/DE/EP/ES/PSO), I am not so sure about using them with Simulated Annealing (SA) as canonical SA operates with a single trial point rather than a population.

Epsilon constraint handling technique as proposed by T. Takahama and S. Sakai, iin their paper "Constrained Optimization by the " Constrained Differential Evolution with an Archive and Gradient-Based Mutation", pp.1680-1688. (Winner of the CEC 2010 competition on constrained single level optimisation)

The Stochastic Ranking Method of Runnarsson and Yao with code in MATLAB and c: https://notendur.hi.is/tpr/index.php?page=software/sres/sres It is easy to get the wrong idea that it only works in Evolutionary Programming (Prof Runarsson and Yao's EA of choice but I have managed to use it as a constraint handling method with Differential Evolution.)

Interestingly one of the simplest and most effective method which I have tried is the method given in Kim et al (2010): T-H Kim, I. Maruta and T. Sugie. A simple and efficient constrained particle swarm optimization and its application to engineering design problems, Proceedings of the Institution of Mechanical Engineers Part C-Journal of Mechanical Engineering Science, Vol. 224, No. C2, pp. 389-400, 2010.

See particularly Equation 2 in this paper. It should be easy to program these in any language of your choice.

Dear Andrew,

Your worthwhile answer is highly appreciated. I looked for the paper titled "A simple and efficient constrained particle swarm optimization and its application to engineering design problems" on the Internet but unfortunately I could not download it.

I would be grateful if you could provide it for me.

Regards,

Morteza

You can add the constraint violation as a penalty in your objective function. 

Dears Andrew, Nesa, and Alireza,

Many thanks for all of your convincing explanations.

Best wishes,

Morteza

The following paper can help you a lot.

E. Mezura-Montes, C.A. Coello Coello, Constraint-handling in

nature-inspired numerical optimization: past, present and future, Swarm and Evolutionary Computation (2011), doi:10.1016/j.swevo.2011.10.001

Dear Zhongyi, and Matthieu,

Thanks for your helpful suggestions.

Best,

Morteza

Dear Morteza,

You can add constraints to the objective function as a penalty function.

I don't see the challenge here? a soft constraint can be modeled as an additional coefficient in the penalty function or just use a very large penalty to represent a hard constraint. Alternatively, you can just do additional checks prior to the evaluation of the objective function to cast out invalid solutions/individuals.

Problems that can be modeled as binary quadratics have many efficient techniques for translating constraints to the objective function via penalty functions.   Gary Kochenberger and Fred Glover have published extensively on the topic of Unconstrained Binary Quadratic optimization.   They also have a tabu search approach named strategic oscillation for working with constraints.

There is a recent survey article on the topic:  

The unconstrained binary quadratic programming problem: a survey, Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang, Yang Wang, Journal of Combinatorial Optimization (Impact Factor: 0.59). 07/2014; 28(1). DOI: 10.1007/s10878-014-9734-0

Article The unconstrained binary quadratic programming problem: A survey

Hi,

You can take penalty function and use it inside the simulated annealing:

objfun(x) + penaltyweight*(sum(abs(equality constraint(i)))+ sum(max(inequalityconstrint(i),0)) )

Another solution consists of two phases: a constraint programming phase to provide an initial solution and a meta-heuristic phase to find the optimal solution. (http://pdf.aminer.org/000/560/131/combining_constraint_programming_and_simulated_annealing_on_university_exam_timetabling.pdf)

The simplest way is using penalty function as penalty for each violations and add them to your cost (fitness) function. There are other ways to handle constraints. One of them is Direct method which uses 4 simple rules for tackling constraints, no mater they are linear or nonlinear. For equality constraints, you have to convert them to inequality equation, it is easy to cope with inequality constraints than equality.

Dear Ali,

Thanks for your comment.

Could you please tell me what "four simple rules" are?

Your most welcome, check this paper, subsection 2.5.

http://www.sciencedirect.com/science/article/pii/S1568494612005108

One of easiest way and of course one of promising method to handle constrains is using penalty function (see the attached paper).

so if your least square objective function is

f=sum ((abs((Ydata - myfunc))./var(Ydata)).^2);

then by using penalty method (as described in the attached paper),  the cost function f is converted into f_c as follow:

q=max(0,c);

for i=1:numel(q)

if q(i) >1

gama(i)=2 ;

theta(i)=300;

elseif 0.1

Penalty function approach works very well with metaheuristic optimization approaches like GA, PSO etc.

https://www.researchgate.net/publication/280244004_A_comparative_study_of_metaheuristic_optimization_approaches_for_directional_overcurrent_relays_coordination

Article A comparative study of metaheuristic optimization approaches...

Search algorithms can be modified to include all other aspects of GA but to restrict the search exclusively within the feasible region.  This eliminates 99.9% of the effort to search among infeasible solution space.  You can check for some of the ideas in this article:

http://link.springer.com/article/10.1023/A%3A1009609820093

Study following articles:

http://www.sciencedirect.com/science/article/pii/S2288430015300439

http://www.tandfonline.com/doi/full/10.1080/15397734.2015.1124023

Hello Murteza,

You could find some information regarding the GA in my work paper.

https://www.researchgate.net/publication/273458746_Intelligent_optimal_tool_selections_for_CNC_programming_of_machine_tools

Best regards,

Afrim Gjelaj

Article Intelligent optimal tool selections for CNC programming of m...

A common way is using penalty function but you can also use feasibility enforcement method

You have different options and the many answers may include many possible ways. Let's imagine we are trying to solve some routing problem such as the TSP. The only constraint is that each cities must be visited.

Option 0: suitable and unsuitable tour are considered. This waste unnecessarily the computing resources.

Option 1: the meta-heuristic operations (i.e. crossover,mutation,local-search, ruin and recreate) ensure every tour is suitable. These operators are specialised to the problem domain, trading generality for specialism.

Option 2: The fitness evaluation (i.e. cost) can penalise heavily the unsuitable tours.

Option 3: A combination between options 1 and 2 are often considered.

Option 4: Consider using some selective or generative hyper-heuristics.

I would recommend you to explore all these options and see what you can do. You may be interested in the work completed for the nurse-rostering problem. Metaheuristic have yet to be as efficient as integer programming. Many interesting papers have been published with meta-heuristics.

P.

Almost any constraint can be added to a heuristic. Many of the responses here are suggesting penalizing potential solutions based on violations of constraints. But more simply, in a heuristic, when a new solution is proposed (a "move" in a s-metaheuristic, for example), constraints can be assessed in the logic and coding prior to formally accepting the move. A number of my older forestry papers illustrate how we have incorporated complex constraints into heuristic processes. See https://petebettinger.weebly.com/publications.html for examples.

There are GA and PSO algorithms in the MATLAB toolbox, you can study the help and learn about the constraints,.But if you have a specific algorithm in mind or you are coding new one, it is better to put the command in the fitness function, if it is correct so it will continue if not it will stop and the result would be a big number which is more than your order number.

By this way, you can remove those unrelated results from your work.

Check the below Links:

Article Topology and Weight Optimization of a 3D Truss by Numerical Method

Article The Topology and Weight Optimization of a Truss Using Imperi...

Have a look on this article, a constraint-handling mechanism to deal with constrained engineering problems

Article Particle Swarm Optimization for solving engineering problems...

1. It is possible to apply logic programming in: (a) Metaheuristic problem (b) Metalearning problem

yes you can add one or more constraints. so you can use a constraint and when the constraint is NOT true, your program does NOT continue or ignore the answer.

you should add your constraint at Optimal function.

for example: There is a function that we like to find an optimal solution and we like to ignore part of the function.

Function's outputs are between "1" and "10". so if outpute is NOT on your constraint , The output value equal more than 10. It is NOT a optimal solution and Delete from responses

Equal

"MATLAB's code"

>> y = Function(x)

>> y= 3*(x^3)+2*(x^2)-x;

%%constraint

>>if y> y=20

>>end

>>end

To sum up, please see the notes below.

-----------------------------------------------------------------

Assume a constrained minimization problem as follows:

Min f(x)

s.t.

gi(x) >= ai ----> Vgi = max { 1 - gi(x)/ai , 0 }

hj(x) Vhj = max { hj(x)/bj - 1 , 0 }

kn(x) = cn ----> Vkn = abs { kn(x)/cn -1 }

where, 'V' means 'Relative Violation' of the constraint and its value for each constraint can be easily determined by MATLAB coding at each iteration of the meta-heuristic algorithm.

==>

Based on this trick, the meta-heuristic algorithm must only minimize the following unconstrained problem:

Min f(x) + Sum(i, Wgi * Vgi ) + Sum(j, Whj * Vhj ) + Sum(n, Wkn * Vkn )

where, 'W' is a weighting factor for each constraint that can be determined by a try-and-error approach or even by another optimization algorithm!

Hi,

I recommend using the oracle method (self adaptative method) for handling constraints in optimization problems by meta-heuristics algorithms. See the following link:

Article The oracle penalty method

The method has been successfully implemented in MIDACO-SOLVER.

"Constraints are handled within MIDACO by the Oracle Penalty Method which is an advanced and self-adaptive method for evolutionary algorithms to reach the global optimal solution. Like all evolutionary algorithms MIDACO does not provide a guarantee to reach the global optimal solution, but extensive numerical tests on hundreds of benchmarks ". See the following link:

http://www.midaco-solver.com/

Regards,

Hello,

You can add such inequalities to their formulation.

I have performed PSO and Genetic Algorithms in both Matlab and R. To start with, the easiest way to run an optimisation method with non-linear constrains with inequalities I can suggest you the R package mco. It is really really easy to input complex constrains.

Good luck!

Francisco-Javier

my suggestion is to include a penalty function in the fitness function.

Hi

You can add contraints as penalized equation like to multiplied fitness equation by zero or an other number.

Good luck

Easily, by using a penalty with the cost function

Hi

Any idea on how to integrate Kohonen SOM with logic programming

I model the constraints of the problem in the mutation/crossover operators, the initial solution and the objective function. For example, I always try to build a feasible initial solution. If it is not possible then in the objective function I attach a penalty. Also, in the mutation and crossover operators, I respect the restrictions and I apply penalized equation in the objective function if they are not met.

Under the most common method, restrictions should be added as part of the objective function with a weight. Therefore, the weight affects negatively the quality of each solution. Under this approach, solution outside feasible región are penalized.

Modeling constraints in the meta-heuristic algorithms are related to the formulation of systems. There is many solutions for example you can integrate the constraints within the objective function.

One way is to use only a Objective function. Then, each constrain is modeled in the function objective as a lagrange mutiplicators. The idea is to punished the solutions outside of the feasible space

In some cases, you can also use also aggregate functions

Selecting the proper constraints handling method is highly reliant on the problem’s nature.