Re: [tablix-list] Using updater functions to restrict domain

From: Tomaz Solc <tomaz.solcREMOVE@THIStablix.org>
Date: Tue Sep 26 2006 - 12:28:53 CEST

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi

> Our first thoughts were to register an updater with A as the source and
> B as the destination, then the updater function would limit the domain
> of B based on the value of A, then we could return some value like -1
> that a modified kernel would then recognize to call domain_rand() to
> make the assignment. However we discovered that domains are only created
> when the XML is parsed, so we thought this would taint the domain for
> future generations.

It is currently impossible (or perhaps only very hard) to change domains
after the XML file has been parsed. This is because the kernel has to
know exactly which resources can be assigned to which events before the
genetic algorithm is started (for example, two genes in the chromosome
can only exchange positions if they have the same domain).

See also compact_domains() function. It processes domains after the XML
has been parsed.

> Another thought we had was to generate the possible domain, but rather
> than using it to call domain_and() we would simply choose a random value
> from the new domain and return that from the updater. With this approach
> we were afraid that we would interfere with the genetic algorithms
> ability to hold onto fit chromosomes, and we have not studied the code
> enough to decide if this approach is essentially equivalent to the last
> one. This would be our ideal solution, but if it will simply randomize
> good chromosomes that are coming in from previous generations then
> perhaps it is not the best choice (but maybe this doesn't matter?).
> We're mainly wondering how returning random (yet limited) values from an
> updater would affect the algorithms efficiency.

The problem here is that the updater function must be deterministic.
There is some logic in the kernel that depends on this and will not work
correctly if the updater function does not always return the same output
value for the same input value.

This is connected with the interaction between updater functions and
domains (domain of a source event for an updater function is changed so
that the domain of the destination event can not be violated). See also
updater_fix_domains() function.

> An obvious solution is to just define a fitness function that makes sure
> event B is in the same week as event A, however since the range of
> possible values is very limited based on the value of event A, we wanted
> to avoid having the genetic algorithm create obviously unsuitable
> solutions. As far as we know this is the idea behind updater functions,
> but they are built not for a possible pool of values but for a specific
> determined value.

I suggest you first try to use a fitness function. It is a simple
solution and unless you have a very large timetabling problem it should
work.

If you are not satisfied with the results obtained this way you can then
try to use a more sophisticated approach. But that would require digging
into the kernel and changing how domains and/or updater functions are
handled. It is possible that in your particular case the
updater_fix_domains() is not needed (for example if there are no
additional restrictions on the time domain of the B event). In that case
I think the second approach you described would be easier to implement.

Also maybe you can somehow predict the week of the A event before the
genetic algorithm is started and update domain for B?

Best regards
Tomaz Solc
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFFGQDlsAlAlRhL9q8RAhXeAJ4/4DRaJw5B5q0/vFPh4B1u/c6XSQCgwpPE
FmjQDkIfYgOQH+AAeleDk6I=
=ckRY
-----END PGP SIGNATURE-----
Received on Tue Sep 26 12:28:56 2006

This archive was generated by hypermail 2.1.8 : Wed Sep 27 2006 - 06:28:49 CEST