Genetic Belief Revisor

GBR (Genetic Belief Revisor) is a system that performs belief revision by means of a multi-agent genetic algorithm. In order to solve a belief revision problem by means of a genetic algorithm, the beliefs are coded as genes in a chromosome and the fitness function that is used is represented by the number of integrity constraints that are satisfied over the total number of constraints.

The genetic algorithm employs a special purpose Lamarckian operator that is able to improve the fitness of a chromosome by means of a logical procedure that checks the beliefs against the constraints. This procedure differs from the belief revision procedure in [5] becausethe Lamarckian operator performs a trade-off between the accuracy of the revision and the computation time: it finds a revision of the theory that is not perfect (usually it satisfies some more constraints) but it takes less time that a full revision.

The genetic algorithm is multi-agent because revision is performed by a pool of agents each possessing the same theory but different integrity constraints. The crossover operator is used to exchange genes among agents.

GBR is written in Sicstus prolog and consists of two files:

The input to gbr is composed by one file defining the theory, the revisables, the number of agents and the distribution of constraints amongst them. The system can also be run in single-agent mode by specifying a single agent in the input file.

A number of parameters can be set in the system (the number of individuals in the population, the fraction of the population to be mutated Lamarckianly and others). Se the comments in the file for the complete list of parameters and of their default values. The value of parameters can be set in the input file.

In order to run GBR, copy both the program files and the input files in the same directory, call sicstus and consult the file
| ?-[gbr].
Then revision can be started
| ?-ga(<file_name>).
The output is written to the file <file_name>.out

Two sample input files are available describing the problem of diagnosing the voter circuit from the ISCAS85 benchmark

Please send an e-mail to Fabrizio Riguzzi if you download the code. Contact him also to report comments, bugs and new experiments.


[1] E. Lamma, L. M. Pereira,and F. Riguzzi, "Logic Aided Lamarckian Evolution", Proceedings of the Fifth International Workshop on Multistrategy Learning (MSL2000), Guimaraes, Portugal, June 2000.

[2] E. Lamma, F. Riguzzi, L. M. Pereira, "Belief Revision by Lamarckian Evolution", First European Workshop on Evolutionary Learning (EvoLEARN2001), Springer-Verlag, LNCS, April 2001 (abstract)

[3] E. Lamma, F. Riguzzi, L. M. Pereira, "Belief Revision by Multi-Agent Genetic Search", submitted for publications

[4] J. J. Alferes and L. M. Pereira, Reasoning with Logic Programming, volume 1111 of LNAI, Springer-Verlag, 1996.

[5] L. M. Pereira, C. V. Damasio, and J. J. Alferes. "Diagnosis and debugging as contradiction removal", In L. M. Pereira and A. Nerode, (eds), Proceedings of the 2nd International Workshop on Logic Programming and Non-monotonic Reasoning, pages 316--330. MIT Press, 1993.


Mail Your Comments on these Pages to the LIA WebMaster Mail Your Comments for LIA to the LIA PostMaster

Back to the LIA Home Page Back to the LIA Who's Who Page
Go to the DEIS Staff Page

Go to the DEIS Home Page Go to the Alma Mater Home Page