1
$\begingroup$

I have a genetic algorithm for a vehicle routing problem with time windows and I need to implement certain modifications. I am not sure what would be the best chromosome representations.

I have tasks which can be divided into 3 sub-tasks with certain ordered time windows, they have to processed in order and all 3 (they represent collecting certain goods in a storage, delivering them and returning packaging to another storage). In the algorithm crossover part these tasks are combined together and evaluated. They have to processed in order according to their task number, i.e. combination "A1, B1, B2, A2, B3, A3" is correct, but "A1, B2, A2, B3, A3, B1" or "A1, A2, B1" is not. The problem is, I don't know how to assure the order of events will be kept. How can I represent this demand in chromosomes? Or, where in the algorithm should I keep this demand?

In the previous version of the algorithm we used only the whole task A or B without distinguishing the subtasks, which is now not sufficient. I am relatively new to genetic algorithms, so pardon me if it's something obvious.

$\endgroup$
0
$\begingroup$

Given you want to maximize fitness function $\phi:\Bbb{R}^n\rightarrow\Bbb{R}$, make $\phi(\vec{x})=-\infty\ \forall \vec{x}\ \notin X$ where the feasible region is $X\subset \Bbb{R}^n$. Then you can initialize the population $P=\{p\ |\ p\in X\}$ and if the GA tries any $p\notin X$, that solution would be killed off. This forces the GA to "learn" the feasible region.

$\endgroup$
2
  • $\begingroup$ so, if I get it right, I do not have to care as much about possible representations in chromosome but rather treat the solution feasibility in the fitness function? Thanks. $\endgroup$ Sep 11 '20 at 20:28
  • $\begingroup$ Yup! However, note that there are pros and cons to both ways: the approach I suggested is pretty universally applicable, which makes it much easier if you ever wanted to change your GA in some way (like if your problem changes again). However, it also might make it less efficient than if you could cleverly enforce crossover/mutation etc to not violate your rules. (Assuming that the extra steps to enforce the rules don't yield a net loss in efficiency). I'm not sure how you'd accomplish the latter, but it'd also make it much more painful to adapt if/when you change the GA. $\endgroup$ Sep 11 '20 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.