I'm trying to use GA to solve a fairly simple scheduling problem with a set of agents. Agents are just moving entities that have simple and predictable trajectories. They need to "capture" information of their environment but have limited resources to do so. The environment is just a 2D space where certain locations provide higher reward to agents if they capture its information.

I want agents to schedule what's best for them based on these reward figures while maintaining resource constraints (essentially to maintain the capacity of an arbitrary resource $C > 0$.) I also want agents to be able to schedule as much tasks as necessary, within fixed boundaries (e.g. max. 10 tasks.)

With these premises, I've modelled GA chromosomes like a matrix:

(E) (T start) (T duration)
  0    1234.5       1000.0 ---> task 1
  1     756.8        392.7 ---> task 2
...       ...          ...
  X      SSSS         DDDD ---> task N

Each row corresponds to a task slot that can either be used ($E=1$) or not ($E=0$). The second and third column are the start and duration times of each task slot. Crossover is performed on multiple horizontal points; parent selection is carried out with the tournament selection operator and combination of parents and children is implemented as truncation.

Chromosome fitnesses are computed as the aggregation of rewards for each captured location (ie. the reward obtained with enabled task slots). I then check constraint satisfaction for the solution and modify their fitnesses accordingly: if resource capacities are violated, $F = F · 10^{-20}$ (left unchanged otherwise). This allows me to still sort populations and keep using tournament selection.

My problem is that my algorithm does not converge because all individuals tend to increase their task durations to a point in which resource constraints are never satisfied. Would there be a better way of modelling such chromosomes or the constraint?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.