CHAPTER 25

Remote Optimization Service

J. GARCÍA-NIETO, F. CHICANO, and E. ALBA

Universidad de Málaga, Spain

25.1 INTRODUCTION

Optimization problems are commonly tackled every day in the academic, industrial, and private domains, but only a few use optimization algorithms for solving their problems, especially in the industrial domain. The rest do not use optimization techniques because they do not know these techniques, they do not have enough knowledge to implement them or working with libraries, or they do not have the hardware resources required to work with the techniques.

In the literature we can find a plethora of libraries of optimization algorithms implemented in different programming languages [21], all with their own advantages and drawbacks. A common characteristic in almost all current related works is the use of XML [20], which facilitates the development of applications in such tasks as new algorithm creation, automatic code generation from XML specifications, integration of algorithms in services for its execution, and XML serialization of methods and objects. However, these libraries can only be used by people knowing the programming language in which the library is implemented, and even in this way, some time is required to be familiar with the algorithms.

In recent years, systems that integrate libraries of metaheuristic, exact, and hybrid algorithms have appeared. In addition, it is always interesting to offer methodologies and services for making the use of software repositories easier in order to make accessible algorithms, such as optimization algorithms, that can be beneficial for a lot of people in the world. In this context, ROS, the remote optimization service [3,10], ROS (Remote Optimization Service) provides a service for the remote execution of optimization algorithms through Internet. ROS is able to manage the access and execution of optimization algorithms, completely different themselves, and probably implemented in different programming languages.

The rest of the chapter is organized as follows. The foundations of ROS and the state of the art of similar services are depicted in Section 25.2. Section 25.3 describes the ROS architecture, entities, components, and main features. In Section 25.4 the technology used in the communication layer of ROS is detailed, and the XML document specification used for the data exchange is introduced in Section 25.5. Section 25.6 covers the mechanism for encapsulating algorithms through Wrappers. Finally, in Section 25.7 the performance of ROS is evaluated using different optimization problems and algorithms, and Section 25.8 concludes the chapter.

25.2 BACKGROUND AND STATE OF THE ART

The objective of an optimization algorithm is to find the best of all possible solutions to a problem. Research in optimization has been very important in computer science from the beginning. Optimization is a very dynamic research field because new challenges appear every day: new engineering problems, new industrial situations, new services that need optimization, and a long list of other situations that constantly challenge the existing optimization techniques [11].

ROS was developed with the objective of establishing an optimization service on the Internet, that is, for easing the access and use of multiple optimization algorithms. In this way, different algorithms developed by different developers in different programming languages are grouped in a repository reachable from anywhere in the world through the Internet. In ROS we distinguish two types of actors: the developer, who provides algorithms and includes them in the system, and the user, who can interact with the available algorithms in a remote way for solving optimization problems.

Several recent initiatives exist presenting common features with ROS. In Table 25.1 we present these state-of-the-art systems together with some of their features. In particular, we show the operation mode (local or distributed) if they use XML for storing or exchanging information, the programming language, the way in which the algorithms are specified, and if they have a graphical user interface. In the last row we present the features of ROS in order to offer an early idea of its properties, allowing a fast comparison against existing proposals. In the following we are going to highlight the more interesting features of each system.

EAML is a language [1,20] based on XML that can be used for specifying evolutionary algorithms using tags defined in a dictionary (DTD [12]). From the EAML specification of the algorithm it is possible to generate C++ source code using a compiler called ECC (evolutionary computation compiler). EAML does not offer generic tags for extending the language and introducing new elements: When a new element has to be included in the language, its dictionary (DTD) must be modified. OPEAL is a library that includes evolutionary algorithms implemented using an extended version of EAML [14]. This library has the possibility of performing distributed executions using SOAP [15].

TABLE 25.1 Brief Summary of State-of-the-Art Systems Related to ROS

The web service eaWeb [9] offers an optimization service based on evolutionary algorithms. The user must specify the objective function and the parameters of the algorithm using XML documents from a web browser, and the service returns the results of the optimization process. The underlying idea of the system is similar to that of ROS, but unlike the latter, eaWeb restricts the types of algorithms, data structures, and parameters to use.

Another available tool is eaLib, a Java class library with which a developer with evolutionary computation knowledge can easily implement evolutionary algorithms. In addition, it includes a serialization mechanism for generating XML documents from solution collections. eaLib is not oriented to the remote execution of algorithms, but to the design of new evolutionary algorithms.

Evolvica is a successor of eaLib that provides a graphical user interface (GUI) for the development of evolutionary algorithms. This system is based on the Eclipse platform [2] and includes a Java editor, a debugger, and a visual results analyzer. It is aimed at expert users with knowledge of the Java language and evolutionary computation.

Finally, EAVisualizer [7] is another application implemented in Java. In this case the user does not need knowledge of Java language or of other programming languages, since in this system it is possible to design an evolutionary algorithm by interactively selecting the various components of the algorithm (operators, individual representation, etc.) from components defined previously.

Our proposal, ROS, has been designed to put together all the advantages of the systems mentioned. On the one hand, as in EAML and OPEAL, XML documents are used in ROS. However, unlike these systems, in this case they contain data involved in execution of the algorithm: parameters, results, execution orders, and so on. Instead of using languages for specifying the evolutionary algorithms, ROS incorporates algorithms already implemented by different developers. It perceives the algorithms as black boxes, where it introduces parameters and receives results, either locally or from a remote execution. Thanks to this feature, ROS is capable of working with many heterogeneous algorithms by different programmers and allocated remotely.

In all the systems presented (except eaWeb), the algorithms must be implemented in Java using the classes and components provided. This restriction is an important drawback for developers who want to include an algorithm implemented in a different programming language. The restriction to the use of Java is that the set of algorithms available in the system is a subset of those that could be included if no restriction would exist. To overcame this drawback, ROS provides a mechanism based on the wrapper design pattern, which allows it to include algorithms implemented in any programming language. All these algorithms can be used simultaneously in a transparent way for the client. For example, a genetic algorithm implemented in C++ can be solving an optimization problem for a user at the same time that an evolutionary strategy implemented in Modula 2 is solving another optimization problem for a second user.

In addition to the features mentioned, ROS also offers graphical user interfaces to ease the interaction with the system, as EAVisualizer, Evolvica, and eaWeb do.

25.3 ROS ARCHITECTURE

To provide a multiplatform and distributed nature to ROS, it was implemented in Java language and is composed of a set of entities interconnected using the client/server (C/S) paradigm. The architecture of ROS is based on four types of entity:

1. The client (see Figure 25.1) is an application that offers a graphical interface to users for interacting with the system. With this interface the users can carry out administrative operations (such as registration and authentication) as well as operations related to resolution of the optimization problems: selection of the algorithms to be applied, configuration of the algorithms selected (parameter setting, machines to run, definition of the objective function, etc.), execution control, and results collection.

2. The primary server is responsible for user authentication. It also offers information about algorithms and machines available to the user. By means of XML configuration documents, the primary server stores the information related to the algorithms implemented in each distribution server.

3. The distribution server (server in Figure 25.1) is a bridge between the client and the machine running the algorithm (worker). The distribution server is therefore a fundamental piece to make ROS scalable, flexible, and distributed in a network of workstations, since it hides the real location of the workers and controls the load balancing among them.

4. The worker houses the algorithms and executes them according to the orders specified by the client and routed through the distribution server. Once an execution is finished, it sends the results to the distribution server, which forwards them to the client.

Figure 25.1 ROS architecture.

Once we have presented the four entities of the system, we are going to detail the data flow sequence through the system in a normal operation. We follow the numeration and direction of dashed lines in Figure 25.1.

1. User authentication. First, the user fills the initial form of the ROS client GUI panel with his or her identification and password, and then it connects to the primary server. Once the user is authenticated in the system, the primary server returns a message of acceptance or rejection.

2. Selection of algorithm, server, and programming language. In this phase, the primary server sends a list of available algorithms, distribution server addresses, and programming languages. The client receives this information and shows it to the user, who makes a selection.

3. Algorithm configuration. The client, based on the algorithm, server, and programming language selected in the previous step, asks the distribution server the specific parameters and configuration options that the user must fill in order to run the algorithm. These parameters and options are specified in a XML document with empty tags that the client must fill with the data provided by the user. Thus, depending on the XML tags, the client generates a specific GUI panel view for each algorithm selected.

4. Algorithm execution. Once the user sets the parameters of the algorithm chosen by means of the visual panel, the XML document is filled by the client and subsequently, sent to the distribution server. This server sends the XML document to the suitable worker, which starts execution of the algorithm.

5. Results collection. After the end of algorithm execution, the results are sent in an XML document to the distribution server, which forwards them to the client. Finally, the client shows the user the results of such execution in the visual panel.

One of the most important issues that the user is required to specify is the fitness function. To do this, the user must provide a function implemented in the same programming language as the algorithm selected and with a given name and signature determined by the algorithm. This function is updated together with the configuration options to the distribution server, which forwards it to the worker. In the worker, the function is compiled together with the algorithm, following the compiling instructions given by the developer of the algorithm.

25.4 INFORMATION EXCHANGE IN ROS

Due to the distributed nature of ROS, it needs to exchange information among its entities, which generally are deployed in different machines. Two versions of ROS are available, depending on the communication interface used: RPC with SOAP and sockets. In the SOAP version, information is exchanged by means of remote procedure calls between web services. The distribution server communicates with the process servers via RPC/SOAP, and the client communicates in the same way with the distribution server (see Figure 25.2). The advantage of using SOAP is that the different entities of ROS can run as web services and can be distributed geographically in a WAN (wide area network) with minimum risk that the communications will be cut by firewalls and other tools for implementing security policies.

The requirement to install web servers for remote object registry implies an additional complexity and computational charge in the system. For this reason, an implementation of ROS using Java sockets for the communication was also developed, making the communication lighter (since sockets are in a lower level with respect to RPC/SOAP) and avoiding an excessive computational charge. To avoid connectivity problems (due to firewalls, for example), this version of ROS should use the TCP 80 port. In the current implementation we use the TCP port 4000.

Figure 25.2 Summarized scheme of the SOAP version of ROS.

25.5 XML IN ROS

The main advantage of XML is that it is a standard for the specification of data. It makes the exchange of information among the different components of an application or even among different applications easy by imposing a set of rules on the data document elaboration. In ROS, XML is used to specify the configuration of a given algorithm and return the results to the client. The information contained in an XML document includes user information, features about the implementation of the algorithm, programming language, input parameters, and results.

All the XML documents that flow through the system are specified following the DTD (data type document) specification optimization_algorithm.dtd specially designed for this service (Figure 25.3, right). As we can see in Figure 25.3 (left), each document is organized hierarchically so that there is a root element <optimization_algorithm>, which contains four elements:

• The <client> element, containing all the user/client information (IP, user ID, etc.)
• The <features> element, containing information related to the features of the algorithm chosen (programming language, compilation/execution orders, etc.)
• The <params> element, which contains the parameters of the algorithm (mutation probability, number of individuals, fitness function, etc.)
• The <results> element, which contains the results of an execution (quality of solutions, computation time, number of evaluations, etc.)

There is an additional element that can be included inside the root element: <others>. This element allows us to specify additional features not included in the current DTD document. This is a mechanism to extend the expressive potential of the XML documents used in ROS.

Initially, an XML document is generated in the distribution server using the information collected from the user. In this phase, the user information and the features of the algorithm selected are included under the <client> and <features> tags of the XML document, respectively. When the user specifies the algorithm and the parameters, this information is included under the <params> element: The algorithm selected is specified by means of an attribute, <params type = algorithm>, and the parameters are included as subtags of the <params> tag. The resulting XML document is sent to the target worker through the distribution server. The worker reads the XML document in order to configure the algorithm and starts the execution. When the execution finishes, the worker collects all the results and includes it under the <results> tag of the XML document. This document is finally sent back to the user through the distribution server.

Figure 25.3 (a) XML document associated with an evolutionary strategy algorithm; (b) summarized DTD file employed to validate all XML documents in ROS.

25.6 WRAPPERS

To be able to include in ROS a large number of algorithms implemented in different programming languages (C, C++, Java, Modula 2, etc.), we must use a general interface for dealing with the algorithms. We use the wrapper design pattern for this task. There is an abstract class called Wrapper that provides methods for generating configuration files from the XML document, launching compilation/execution orders, and writing the results in the XML document. In order to include a new algorithm in ROS, the developer must create a subclass of Wrapper and implement all previous methods of dealing with the algorithm. This subclass encapsulates all the details associated with the algorithm and allows ROS to communicate with the algorithm in a homogeneous way.

Figure 25.4 Algorithm encapsulation in ROS using the wrapper design pattern.

Figure 25.4 illustrates how the wrapper design pattern works in ROS. Let us suppose that we have an evolutionary strategy algorithm in ROS and that its associated Wrapper subclass is Wrapper_es. Initially (step 1 in Figure 25.4), the process server (worker) obtains the XML document with the configuration data of the algorithm from the distribution server. Then the worker invokes a method of Wrapper_es for generating the configuration file (specific to the available implementation of the evolutionary strategy) from the XML document (step 2). After that, the worker extracts the compilation command (if needed) in order to generate an executable file. The next step consists of running the algorithm using the execution command provided by Wrapper_es (step 3). When the execution finishes, Wrapper_es writes the results obtained into the XML document, which will be returned to the distribution server (steps 4, 5, and 6).

25.7 EVALUATION OF ROS

In this section we evaluate the performance of the system by solving a set of optimization problems with different optimization algorithms. We consider two different configurations of ROS: distributed in a LAN and deployed locally in a single machine. In the distributed configuration, the servers of ROS were executed in four machines with a Pentium-4 processor at 2.4 GHz and 512 Mbytes of RAM memory connected by means of a 100-Mbps fast Ethernet network. These servers are the primary server, one distribution server, and two process servers. One of the process servers is running in a machine with Linux and the other one is running in a machine with Windows. There are some algorithms that can only be executed in a specific operating system (Linux or Windows). Using at least one worker running in each operating system, the user can select all these algorithms. In addition, for those algorithms that can be executed in both operating systems, the user can compare the results obtained by the two implementations. The client application was executed in one machine with a Pentium-4 processor at 2.6 GHz and 512 Mbytes of RAM memory.

In the local configuration all the servers and the client application are running together on the same machine with a Pentium-4 processor at 2.6 GHz and 512 Mbytes of RAM memory. In this case the machine was first booted with Windows to evaluate the algorithms implemented in this operating system and after that we evaluated the Linux algorithms.

Tables 25.2 and 25.3 show the execution time (e.t.) and the communication time (c.t.) obtained after running different algorithms using ROS in both local and distributed configurations. We show the averages and the standard deviations over 50 independent runs.

For a given algorithm, we could expect lower execution times in the local configuration since the machine used is faster. However, we can notice that this does not happen in all cases. In particular, higher execution times in the local configuration are obtained for the cellular evolutionary algorithm (CEA) [5], the distributed evolutionary algorithm (DEA) [4], and the genetic algorithm for solving the problem called Venice Tides (VTGA) [8]. The reason of such an unexpected result could be the computational overload related to the base algorithm (implemented by different authors) and the operating system (previous results not shown confirm this hypothesis). For the remaining algorithms—steady-state genetic algorithm (SSGA) [19], evolutionary strategy (ES) [6], and simulated annealing (SA) [13]—the execution time in the local configuration is lower than in the distributed configuration.

TABLE 25.2 Experimental Results Using ROS with the Local Configuration

TABLE 25.3 Experimental Results Using ROS with the Distributed Configuration

In Figure 25.5 we plot the execution time of the 50 independent runs in the two configurations: distributed and local. We can observe that, as expected, the execution time is more stable in the local configuration. In the LAN configuration the execution time depends on the network traffic, which is unpredictable. If we focus on the communication time (see Figure 25.6), we can observe that more time is required in the LAN configuration since the processes are distributed in a network of workstations. However, in the genetic algorithm for the Venice lagoon problem, the evolutionary strategy, and the cellular genetic algorithm, this does not happen. The reason could be that the communication time includes preprocessing of XML and writing in files, which can slow communication down significantly in the local configuration. As happens with execution time, communication time is more stable in the local configuration.

One of the most important aspects in a study of the behavior of ROS in a network is the measurement of the data flow that arises during information exchange between the various entities. Figure 25.7 consists of two diagrams (generated by means of the network application Etherape [18]), which show the traffic exchanged by the entities of ROS in a typical distributed configuration. Figure 25.7a reflects how the traffic trail generated by the interaction between the client and the primary server is thinner than that generated between the client and the distribution server, since in the second case the XML document is sent (more data). In Figure 25.7b the distribution server carries out a request to the process server. A file-reading operation using the network file system can also be observed.

Figure 25.5 Execution time in the (a) distributed and (b) local configurations.

Figure 25.6 Communication time in the (a) distributed and (b) local configurations.

Figure 25.7 Data flow registered by Etherape in the network during a typical execution of ROS.

25.8 CONCLUSIONS

In this chapter we have described ROS, a web service that provides access to a large set of optimization algorithms for solving optimization problems through the Internet. ROS is a platform-independent system based on client/server architecture that uses XML documents for information exchange. In addition, this service offers a graphical user interface for easing access to the system. From the point of view of the developers, the wrapper design pattern allows them to include new algorithms in any programming language with minimum effort.

As future work we plan to add new algorithms to the system and different implementations of the current algorithms. For dealing with the wide diversity of these algorithms and the different specific parameters that these algorithms require, it is necessary to generalize the XML specification (DTD).

We also defer for future work the study and development of methods for easing the incorporation of new algorithms in the system, imposing common design criteria for the development of these algorithms, developing classes for managing groups of algorithms, and including new graphical user interfaces.

The installation package for ROS is available at http://tracer.lcc.uma.es/ros/index.html. It is possible to evaluate the system by connecting it to active servers already working in our institution, whose IP addresses are configured in the client application.

Acknowledgments

The authors are partially supported by the Spanish Ministry of Science and Technology and FEDER under contract TIN2005-08818-C04-01 (the OPLINK project) and the Spanish Ministry of Industry and EUREKA-CELTIC by FIT-330225-2007-1 (the CARLINK project).

REFERENCES

1. EAML website. http://vision.fhg.de/ veenhuis/eaml/intro.html.

2. Eclipse website. http://www.eclipse.org.

3. E. Alba, J. García-Nieto, and F. Chicano. ROS: servicio de optimización remota. In J. Riquelme and P. Botella, eds., Actas de las JISBD, Barcelona, Spain, pp. 509–514, 2006.

4. E. Alba and J. M. Troya. An analysis of synchronous and asynchronous parallel distributed genetic algorithms with structured and panmictic islands. In Proceedings of the 11 IPPS/SPDP'99, pp. 248–256, 1999.

5. E. Alba and B. Dorronsoro. Cellular genetic algorithms. In Operations Research, vol. 42 of computer Science Series. Springer-Velag, New York, 2008.

6. T. Back, F. Hoffmeister, and H. Schewefel. A survey of evolution strategies. Technical Report D-4600, Department of Computer Science XI, University of Dortmund, Germany, 1991.

7. P. Bosman. Evolutionary algorithm visualization: EAVisualizer GUI. http://www.cs.uu.nl/people/peterb/computer/ea/eavisualizer, 2001.

8. J. C. Hernández C. Luque, and P. Isasi. Forecasting time series by means of evolutionary algorithms. In Proceedings of the PPSN VIII, vol. 3242 of Lecture Notes in Computer Science. Springer-Verlag, New York, pp. 1061–1070, 2004.

9. V. Filipovic. eaWeb: evolutionary algorithm web service. http://www.matf.bg.ac.yu/~vladaf/EaWeb, 2002.

10. J. García-Nieto, E. Alba, and F. Chicano. Using metaheuristic algorithms remotely via ROS. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'07), London, ACM Press, New York, p. 1510, 2007.

11. F. Glover and G. Kochenberger, editors. Handbook of Metaheuristics, vol. 57 of International Series in Operations Research and Management Science. Kluwer Academic, Norwell, MA, 2003.

12. E. R. Harold. XML Bible. IDG Books, Boston, MA 1999.

13. T. W. Manikas and J. T. Cain. Genetic algorithms vs. simulated annealing: a comparison of approaches for solving the circuit partitioning problem. Technical Report 96-101, Department of Electrical Engineering, University of Pittsburgh, Pittsburgh, PA, 1997.

14. J. J. Merelo-Guervós. OPEAL, Una librería de algoritmos evolutivos en Perl. In E. Alba et al. eds., Actas del Primer Congreso Español sobre Algoritmos Evolutivos y Bioinspirados (AEB'02), pp. 54–59, 2002.

15. J. J. Merelo-Guervós, P. A. Castillo Valdivieso, and J. García Castellano. Algoritmos evolutivos P2P usando SOAP. In Proceedings of the Primer Congreso Español sobre Algoritmos Evolutivos y Bioinspirados, Mérida, Mexico, pp. 31–37, 2002.

16. A. Rummler. EALib. http://www.evolvica.org/ealib/index.html, 2002.

17. A. Rummler. Evolvica. http://www.evolvica.org, 2002.

18. J. Toledo, V. Adrighem, R. Ghetta, E. Mann, and F. Peters. Etherape, a graphical network monitor. http://etherape.sourceforge.net/.

19. F. Vavak and T. C. Fogarty. Comparison of steady state and generational genetic algorithms for use in nonstationary environments. Technical Report BS16 1QY. Faculty of Computer Studies and Mathematic, University of the West of England, Bristol, UK, 1996.

20. C. Veenhuis, K. Franke, and M. Köppen. A semantic model for evolutionary computation. In Proceedings of the 6th International Conference on Soft Computing, Iizuka, Japan, pp. 68–73, 2000.

21. S. Voß and D. Woodruff, eds. Optimization Software Class Libraries. Kluwer Academic, Norwell, MA, 2002.