I've already spoken of differential evolution in previous articles (1, 2). It is an optimization algorithm extremely versatile thanks to its absence of requirements on the function to optimize except for using real values (no need for differentiability or even continuity for example). Its algorithm is as follow:

Initialise N candidates randomly FOR each candidate A fitness[A] = Fitness(A) LOOP until end criterion FOR each candidate A Select three other candidates A1, A2, A3 such as A!=A1!=A2!=A3 Select a dimension D at random FOR each dimension D' IF D=D' or rnd() < prob_mutation THEN new_candidate[D'] = A1[D'] + (A2[D'] - A3[D']) * coeff_mutation ELSE new_candidate[D'] = A[D'] new_fitness = Fitness(new_candidate) IF new_fitness < fitness[A] THEN A = new_candidate Return the best of candidates

Its simplicity and versatility make it a great tool to have in one's toolbox. However, it doesn't handle constrained optimization. Modification of the differential evolution algorithm for that kind of problems has been studied in the thesis of Zaakirah Kajee-Bagdadi. Before reading his thesis I came up with a solution which I'm introducing below. My idea similar to the one of his FDEC algorithm (minimizing both fitness and constraints simultaneously, and treating feasible and infeasible candidates separately), and simpler as it doesn't use a penalty function.

The constraints are supposed to be given as a function Constraint(X) such as Constraint(X)>=0.0 if X respects the constraint and Constraint(X)<0.0 else.

FOR each candidate A Initialise A randomly constraint[A] = Constraint(A) LOOP until constraint[A] >= 0.0 or tried more than nb_try_max Initialise A randomly constraint[A] = Constraint(A) fitness[A] = Fitness(A) LOOP until end criterion FOR each candidate A Select three other candidates A1, A2, A3 such as A!=A1!=A2!=A3 Select a dimension D at random FOR each dimension D' IF D=D' or rnd() < prob_mutation THEN new_candidate[D'] = A1[D'] + (A2[D'] - A3[D']) * coeff_mutation ELSE new_candidate[D'] = A[D'] new_constraint = Constraint(new_candidate) IF new_constraint >= 0.0 or constraint[A] < 0.0 new_fitness = Fitness(new_candidate) IF (new_constraint >= 0.0 and constraint[A] < 0.0) or new_fitness < fitness[A] THEN A = new_candidate Return the best of candidates such as constraint[best] >= 0.0

In my implementation I also randomise coeff_mutation (Zaakirah Kajee-Bagdadi does the same), and if there is no feasible candidate at the end of the optimization I return the best of the infeasible ones. The constraint value of the returned candidate allows the user to know if it's a feasible one, and if it is, whether or not relaxing the constraint is likely to improve the fitness (i.e. the candidate lies on the constraint border).

My motivation to add support for constrained problems to differential evolution comes from the implementation of support-vector machine for which a constrained optimization problem needs to be solved. It's still a wip and I've only tried it on two datasets, one with a feasible solution and one without. It worked as expected on both, so I'm looking forward to other occasions to try that enhanced differential evolution algorithm and see how it performs.