4

i work in a research team to solve a multi objective engineering problem and i concentrate on NSGA-II algorithm ,but now i stuck i need to understand how SBX crossover work with numerical example so i can implement it or even if there's a ready made code i can adapt according to our problem but first i need to see numerical example so i can go on,any resource available for that i only found a presentation on http://www.slideshare.net/ but only equations no example.

manlio
  • 18,345
  • 14
  • 76
  • 126
user2963216
  • 391
  • 2
  • 4
  • 11
  • Take a look at this question, it was of geat help to me: http://stackoverflow.com/questions/8918625/simulated-binary-crossover-sbx-crossover-operator-in-scala-genetic-algorithm – Tiago Peres França Sep 07 '16 at 17:47

2 Answers2

4

These days I also spent more time on SBX coz it is a better choice for crossover in number coding problem. I checked the original paper and the slides you pointed out. Although I have not known the complete process of SBX, I can tell you what I have learnt which maybe help you know SBX in a further step.

1:The idea is from binary coding with single point crossover. For instance, the parent chromosome p1 and p2, their children c1 and c2.

2:In binary coding, it has the property: (p1+p2)/2=(c1+c2)/2. We denote |(c1-c2)/(b1-b2)| as beta, and b is sometimes equaled to 1 according to the simulation.

3:When we use this idea with number coding, this property should be retained, for which, an solution for c1 and c2 in number coding:

c1 = (p1+p2)/2 +0.5*beta(p1-p2) and c2 = (p1+p2)/2-0.5*beta(p1-p2) and p1>p2 In further, the value of beta is our goal.

All above are what I learn from SBX. Sorry for it is not complete!

Kevin Sun
  • 452
  • 4
  • 14
  • 1
    Hi guy, now I have finalized the algorithm. Maybe the pseudo-code list below will help to learn this algorithm. if it meets the condition of sbx: choose parent p1 and p2 u = rand(1) if <= 0.5 beta= (2*u)^{1/(n+1)} else beta = 1/(2(1-u)).^{1/(n+1)} c1 = 0.5*[(1+beta)*p1+(1-beta)*p2] c2 = 0.5*[(1-beta)*p1+(1+beta)*p2] sometimes, n is got by {2,3,4,5} or other non-negative value. I hope this will help you! – Kevin Sun Oct 01 '15 at 15:27
1

This question is old, but I recommend reading the academic articles:

  • DEB, Kalyanmoy; AGRAWAL, Ram Bhushan. Simulated binary crossover for continuous search space. Complex systems, v. 9, n. 2, p. 115-148, 1995.
  • VARGAS, Dênis EC. Um Estudo dos Parâmetros do Algoritmo NSGA-II com o operador SBX em Problemas de Otimização Estrutural Multiobjetivo. Proceeding Series of the Brazilian Society of Computational and Applied Mathematics, v. 7, n. 1, 2018.
  • CRUZ, Frederico Rodrigues Borges da et al. Abordagem multiobjetivo para otimização de redes de filas finitas. 2012.

The article available at this link may also be helpful.

There is also a msu-coinlab/pymoo NSGA python implementation on github, where there is a simulated_binary_crossover.py file that contains an implementation that you can build upon.

To calculate the number of children to formulate is:

  • enter image description here
  • enter image description here

AZEVEDO (1) uses different formulas:

  • enter image description here
  • enter image description here

To calculate function of beta (βi), use the probability distribution:

enter image description here

To calculate beta (βi):

enter image description here

η is index of user defined distribution (not negative)

The steps to calculate the float number resulting from the crossover is:

  1. Set a random number µ ~ (0,1);
  2. Calculate the βi to share from the formula above;
  3. Generate children using the formulas above using βi

Adicional Reference:

(1) AZEVEDO, Carlos Renato Belo. Geração de diversidade na otimização dinâmica multiobjetivo evolucionária por paisagens de não-dominância. 2011. Dissertação de Mestrado. Universidade Federal de Pernambuco.

guinalz
  • 37
  • 7