dc.description.abstract |
Evolutionary Algorithm (EA) provides a mechanism that can achieve efficient exploration for design spaces. Thus, it constitutes an efficient tool for identifying the best
alternatives to implement the solution of a certain problem. In a previous work of
Information Technology students, they have applied the EA to the university course
scheduling problem and they have implemented the methodology on a real data
from the College of Administrative Sciences and Informatics at Palestine Polytechnic University (PPU). Two major shortages were founded in their project: First, the
relatively long execution time that takes the evolutionary algorithm to find the optimal solution. Second, the soft constraints were considered in the implementation,
but were not well satisfied.
In this project, we have implemented the EA using parallel programming techniques. This permits to execute the program in a cluster of machines, which in turns
reduces the execution time. In addition, we have applied some soft constraints concurrently with the hard constraints in order to get better results by making the EA
minimizing the soft cost without affecting the hard cost.
Results show that, after redrafting the algorithm to be multi-objective, the soft
cost will go to zero if we use enough individuals and iterations, at the same time
the hard constraints are still satisfied.
In addition, after distributing the algorithm on 7 machines with 11 processors
the obtained speedup reaches 6 on average. |
en_US |