MLULSP ANT Algorithm

This paper contains the result of 6 students work from the University of Applied Sciences Stuttgart formerly known as Hochschule für Technik Stuttgart (www.hft-stuttgart.de) The mentor of this course was Prof. Dr. J. Homberger who manifested the requirements and fundamentals of this problem. The goal was to run a software development team where different people have different roles. Furthermore an algorithm had to be developed with the corresponding distributed system which is also the main result of this work.

The MLULSP (multilevel unconstrained lot sizing problem) is a problem in the NP-complete domain. The optimal solutions (social welfare) of this  supplychain problem can not be calculated for graphs which are significantly bigger that trivial graphs. Therefore an optimization algorithm was needed. First we tried some approaches with EAs (evolutionary algorithms) but switched then back to ANT systems which showed good convergence. The main challange (for our team) was not only to implement the ANT system for this problem domain, rather the objective was to distribute the ANT system on agents. One ANT system could find a good solution on its own, but we had to divide the update layer into agents which evaluate all contracts separate and on its own. Information hiding is applied here. It is clear to see that with n agents with conflictive objectives lead to bad convergence. The objective was: to find an algorithm which negotiates between agent to find a compromise to achieve social welfare (all agents are happy). Read the paper to get a more detailed picture of the overall problem!

  • My very special part was the development and implementation of the negotiation algorithm which forms the base for this problem.
  • Furthermore I implemented the ANT system and created a Java Framework for distributed agent-based algorithms.
  • (The base graph representation idea, in fact the ant system, was proposed by Prof. Dr. J. Homberger)
  • Only run Class2 problem data from this Webstart (denoted with „ph2*“ for example „ph2in3.req“).
  • This is because your VM needs 1GB RAM for Class3 problem data and Webstart doesn‘ allow this.
  • For Class3 just download the JAR file and run with -Xmx1024M
  • For Class2 problem data select Leadtime=0 and for Class3 Leadtime=1

CooperationAntSystem.pdf (The complete paper and algorithm description)

Presentation.pdf (10 Minute introduction to the solution baseidea)

Download full Java Sourcecode (5,85 MB)

Read this document on Scribd: CooperationAntSystem

Schreibe einen Kommentar