This is the most updated web site for the sub-project TIC99-0754-C03-03 developed at the University of Málaga (UMA) inside the core project MALLBA.

MALLBA is a CICYT funded project made up of three subprojects located in research groups developing their work at the University of Málaga (UMA), the University of La Laguna (ULL) and the University Politechnique of Cataluņa (UPC) (MAlaga+La Laguna+BArcelona=MALLBA). They are all in SPAIN; the last link (UPC) holds the information of the whole project statements.

The main goal of the MALLBA project is to develop generic optimization software skeletons that run in sequential, LAN and WAN environments. There are lots of added value sub-goals to this general statement:

• Transparency: the main goal is expected to be accomplished transparently to favor un-experienced users,
• Efficiency: all the provided algorithms are expected to be competitive in their niche of application, especialy when run in parallel
• Genericity: all the software is developed in C++ providing general code to create an open library as well as many full-featured skeleton instances solving a variety of problems,
• Easy extensibility: so that the user can directly run his/her algorithms in seq/LAN/WAN and also powered to run in Internet environments.

The major achievements in this sub-project are defined in the development of hybrid and parallel algorithm skeletons. The goal of our sub-project can be roughly stated as designing and implementing combination of heuristic and exact algorithm skeletons to achieve more efficient and accurate optimization procedures.

The project is scheduled to offer annual results in terms of new skeletons in the three above mentioned environments: sequential, local area network and wide area network. The main outcomes of every year will be new releases of the mallba library in each evnvironment, although many other related stuff will also be developed in order to understand and ease the work of the project. Some examples of such a work will be a common communication module to program the parallel skeletons, measurements to model the connectivity of our three research centers, preliminary numerical results to guide the implementations, and a benchmark of problems solved with the developed instances. Herein we summarize the results of our sub-project on heuristic algorithms.

YEAR 2000 (first project year)

This year the goal is to provide sequential skeletons as well as to forecast and create stuff to sustent the developments of the second year.To achieve these goals we have studied the requirements of a skeleton system in order to support hybrid methods combining heuristic and exact procedures in a general way (working document on hybrids).

The general conclusion of this analysis is that the skeletons to be hybridized needs a public interface to access and to modify their search state, in order to merge two or more algorithms in the bybrid version. A second result in this study is the necessity of allowing slicing of the algorithms in that they must allow separate execution of atomic search operations, in order a hybrid algorithm could take advantage of this facility to merge the execution steps of several skeletons to yield a new(hopefully more efficient) hybrid algorithm.

Then, we deeply studied the different alternatives to implement a basic communication module to be used in the next phase (working document on middleware of May 30 2000). This study showed MPI as the best choice for our project due to its efficiency, standardization and goo perspectives of future releases. Other message passing librarie such as PVM, LEGION, and other different paradigms such as OpenMP or BSP were considered but judged unsuitable for our goals. Using Java-RMI, Globus or CORBA is, at this point, still under consideration. Also, it is planned to support LEDA objects in the communication module.

YEAR 2001 (second project year)

This second year is devoted to implementing LAN skeletons of hybrid algorithms.

First of all, we have made a revision of the communication module services (revised document on middleware January 30 2001). Here, we first introduced NetStream, a C++ library implemented on MPI whose major achievement is to be quite easy to use and that represents a point to future enhacements for the LAN and WAN phases of the MALLBA project. Although LEDA objects were initially considered, they were definitely left out in new versions coming after NetStream v1.0.

At present, NetStream v1.6 is available, allowing users to send many basic types, both raw and packed, and providing methods to create group of processes in order to model the third phase of WAN (linked clusters) utilization. The basic interface, examples of use and performance evaluation graphs are showed in the precedent link to provide a self-contained information about this library. An HTML on-line version explaining NetStream v1.6 can be reached by clicking here.

As to the main goal of developing hybrid LAN skeletons we already made some progress and have almost finished the work for this year (click here to get a summary of results in Spanish):

• We have developed a brand new skeleton for genetic algorithms (GA's), what really comprises several algorithms, namely a GA(m+l), a GA(m,l), with many capabilities to behave as other classes of evolutionary algorithms (EA's) with changes in operators and with new features to include local search techniques. State information to deal with hybrids is full operative.
• Also, we have developed a new simulated annealing (SA) skeleton with state information accesibe to the environment, in order to run it alone or as a hybrid procedure.
• Some hybrids relating GA and branch and bound (B&B) have been developed. Also, hybrid algorithms which potentially can use different parameters and behave in a different way have been dealt with in order to simulate skeleton combinations and to study to which extent state information is imperative.
• Several hybrids have been developed. GASA1 executes a GA that applied local search by including SA as an additional operator applied after recombination and mutation. GASA2 first completely executes a GA and then applies SA on a set of selected individual from the final population of the GA; random and fitness proportional selection have been tested.
• Different LAN parallel extensions have been developed for GA, SA, GASA1 and GASA2. Basically, the underlying parallel paradigm executes several copies of its sequential counterpart with an added migration step in a unidirectional ring of skeletons.

We have addressed several optimization problems. Some of them are pure combinatorial optimization tasks, such as the maximum cut problem in graphs. Some others are applications of such class of problems, like assigning communication frequencies to cellular phone links, designing error correcting codes for optimal transmission of information through a noisy communication network or solving lab problems to assess the functionalities of the developed skeletons.

Some of the publications of these, and other related stuff, made by our group in Málaga are these:

1. E. Alba, A.J. Nebro, J.M. Troya, Heterogeneous Computing and Parallel Genetic Algorithms, Journal of Parallel and Distributed Computing, 2001 (to appear)
2. E. Alba, Parallel Evolutionary Algorithms Can Achieve Super-Linear Performance, Information Processing Letters, 2001 (en prensa)
3. E. Alba, J.M. Troya, Gaining New Fields of Application for OOP: the Parallel Evolutionary Algorithm Case, The Journal of Object-Oriented Programming, 2001 (to appear)
4. E. Alba, J.M. Troya, Improving Flexibility and Efficiency by Adding Parallelism to Genetic Algorithms, Statistics and Computing, 2001 (to appear)
5. E. Alba, J.M. Troya, Analyzing Synchronous and Asynchronous Parallel Distributed Genetic Algorithms, Future Generation Computer Systems, 17(4):451-465, January 2001
6. Alba, S. Khuri, Applying Evolutionary Algorithms to Combinatorial Optimization Problems, Alexandrov V.N., Dongara J.J., Juliano B.A., Renner R.S., Tan C.J.K. (eds.), Proceedings of the International Conference on Computational Science (ICCS'01), LNCS vol. 2074, Part II, Springer-Verlag, Berlin, Heidelberg, pp. 689-700, 2001
7. C. Cotta, E. Alba, R. Sagarna, P. Larrañaga, Adjusting Weights in Artificial Neural Networks using Evolutionary Algorithms, P. Larrañaga, J.A. Lozano (eds.) Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation, chapter 18, pp. 357-373, Kluwer Academic Publishers, 2001
8. C. Cotta, J.M. Troya, Analyzing Directed Acyclic Graph Recombination, Computational Intelligence: Theory and Applications, B. Reusch (ed.), Lecture Notes in Computer Science 2206, pp. 739-748, Springer-Verlag Berlin, 2001
9. R.E. Berretta, C. Cotta, P. Moscato, Forma Analysis and New Heuristic Ideas for the Number Partitioning Problem, Metaheuristics International Conference, pp. 337-341, Oporto, 2001
10. C. Cotta, J.M. Troya, A Comparison of Several Evolutionary Heuristics for the Frequency Assignment Problem, Connectionist Models of Neurons, Learning Processes, and Artificial Intelligence, J. Mira, A. Prieto (eds.), Lecture Notes in Computer Science 2084, pp. 709-716, Springer-Verlag Berlin, 2001
11. M. Díaz, B. Rubio, E. Soler, J.M Troya, DIP: a Pattern-based Approach for Task and Data Parallelism Integration. The 16th ACM Symposium on Applied Computing (SAC'2001). Special Track on Coordination Models, Languages and Applications. Las Vegas, Nevada (USA), Marzo 2001.
12. M. Díaz, B. Rubio, E. Soler, J.M Troya, Integrating Task and Data Parallelism by means of Coordination Patterns. The 6th International Workshop on High-level Parallel Programming Models and Supportive Environments (HIPS'2001). LNCS vol. 2026, Springer-Verlag, pp. 16-27. San Francisco, California (USA), Abril 2001.
13. M. Díaz, B. Rubio, E. Soler, J.M Troya, A Pattern-based Language to Coordinate HPF tasks, Primeras Jornadas sobre Lenguajes de Programación (PROLE'2001). En prensa. Almagro (Ciudad Real), Noviembre 2001.
14. M. Díaz, B. Rubio, E. Soler, J.M Troya, A Border-based Coordination Language for Integrating Task and Data Parallelism, Journal of Parallel and Distributed Computing, 2001 (to appear).

YEAR 2002 (third and final project year)

Since we are at present finishing the next (LAN) release of the MALLBA library, the main activity consists in sticking the sub-projects results together and to anticipate the needs of the final year. The foreseen activies are those:

• Integrating all the software in a single tool.
• Coordination activities to decide the ways to cope with the WAN extension of the presently existing skeletons.
• Evaluating simple algorithmic skeletons in the WAN, to later extend them to solve combinatorial optimization problems. We sill consider, not only medium-sized problem instances, but also real-world benchmarks needing the support of a geographically distributed system.
• Analyzing the impact of using asynchronous and loosely coupled algorithms in the WAN.
• Extending the behavior of NetStream v1.6.
• Analyzing coordination models developed for data parallelism to comare the results against a more traditional message passing system.
• Dissemination of the results in talks, conferences and journals.
• Open all the information managed and created inside the project to the international research community through our sub-project Web sites.

This site has been developed and mantained by Enrique Alba

Noviembre 16, 2001