Scalarization functions represent preferences in multi-objective optimization by mapping the vector of objectives to a single real value. Optimization techniques using scalarized preferences mainly focus on obtaining only a single global preference optimum. Instead, we propose considering all local and global scalarization optima on the global Pareto front. These points represent the best choice in their immediate neighborhood. Additionally, they are usually sufficiently far apart in the objective space to present themselves as true alternatives if the scalarization function cannot capture every detail of the decision maker's true preference. We propose an algorithmic framework for obtaining all scalarization optima of a multi-objective optimization problem. In said framework, an approximation of the global Pareto front is obtained, from which neighborhoods of local optima are identified. Local optimization algorithms are then applied to identify the optimum of every neighborhood. In this way, we have an optima-based approximation of the global Pareto front based on the underlying scalarization function. A computational study reveals that local optimization algorithms must be carefully configured for being able to find all optima.

Scalarization techniques are a popular method for articulating preferences in solving multi-objective optimization problems. These techniques, however, have so far proven to be ill-suited in finding a preference-driven approximation that still captures the Pareto front in its entirety. Therefore, we propose a new concept that defines an optimal distribution of points on the front given a specific scalarization function. It is proven that such an approximation exists for every real-valued problem irrespective of the shape of the corresponding front under some very mild conditions. We also show that our approach works well in obtaining an equidistant approximation of the Pareto front if no specific preference is articulated. Our analysis is complemented by the presentation of a new algorithm that implements the aforementioned concept. We provide in-depth simulation results to demonstrate the performance of our algorithm. The analysis also reveals that our algorithm is able to outperform current state-of-the-art algorithms on many popular benchmark problems.

In energy systems, the transition from traditional, centralized architecture and controllable generation to an ever more decentralized and volatile generation due to an increasing use of renewable energy sources arises new challenges for the management and balancing of the electricity grid. These can be met through energy management systems (EMS) that enable flexible consumption and production of energy on the demand side of the grid. The EMS for smart buildings that is used within this paper allows for the integration of a multitude of devices through an architectural approach which is similar to “plug-and-play”. These devices can then be optimized to a flexible load shape by an Evolutionary Algorithm (EA). The differentiated optimization capabilities of the devices require adequate encoding schemes. Such schemes are the major contribution of this paper. The aptitude of these encodings is shown and validated through the simulation of smart buildings with different configurations, both concerning quantitative and qualitative benefits to be achieved according to energy systems' transition and users' objectives.

Coal blending processes mainly use static and non-reactive blending methods like the well-known Chevron stacking. Although real-time quality measurement techniques such as online X-ray fluorescence measurements are available, the possibility to explore a dynamic adaptation of the blending process to the current quality data obtained using these techniques has not been explored. A dynamic adaptation helps to mix the coal from different mines in an optimal way and deliver a homogeneous product. The paper formulates homogenization of coal in longitudinal blending beds as a bi-objective problem of minimizing the variance of the cross-sectional quality and minimizing the height variance of the coal heap in the blending bed. We propose a cone based evolutionary algorithm to explore different trade-off regions of the Pareto front. A pronounced knee region on the Pareto front is found and is investigated in detail using a knee search algorithm. There are many interesting problem insights that are gained by examining the solutions found in different regions. In addition, all the knee solutions outperform the traditional Chevron stacking method.

Many multi-objective algorithms use volume based quality indicators to approximate the Pareto front. Amongst these, the hypervolume is the most widely used. The distribution of solution sets of finite size μ that maximize the hypervolume have been investigated theoretically. But nearly all results are limited to the bi-objective case. In this paper, many of these results are extended to higher dimensions and a theoretical analysis and characterization of optimal $\mu$-distributions is done. We investigate monotonic Pareto curves that are embedded in three and higher dimensions that keep the property of the bi-objective case that only few points are determining the hypervolume contribution of a point. For finite μ, we consider the influence of the choice of the reference point and determine sufficient conditions that assure the extreme points of the Pareto curves to be included in an optimal μ- distribution. We state conditions about the slope of the front that makes it impossible to include the extremes. Furthermore, we prove more specific results for three dimensional linear Pareto fronts. It is shown that the equispaced property of an optimal distribution for a line in two dimensions does not hold in higher dimensions. We additionally investigate hypervolume in general dimensions and problems with cone domination structures.

This paper presents a new decentralized approach for evacuating a large number of people from a building using mobile devices which can communicate locally with each other. We investigate the impact of the local communication between the devices on the evacuation by proposing a new distributed evacuation planning algorithm called Distributed Swarm Evacuation Planning. The main challenge in this approach concerns the local communication, which can be unreliable, incomplete, and delayed. Experiments show that we can significantly reduce the evacuation time compared to a modeled panic-like evacuation scenario and that the results are better than those of a shortest-path evacuation plan.

Mobile ad hoc networks (MANETs) are gaining increasing significance with computing devices becoming ubiquitous and equipped with wireless communication modules. Many applications for such networks require the devices to know their position within the network or their distance to other devices. Precise determination of these parameters often fails due to lack of information, missing hardware, or inaccessibility of needed resources, making an approximation necessary. We introduce an algorithm to calculate hop counts and, thereby, derive distances between devices. The algorithm is based on synchronization of all devices in the MANET. We show that an intentional phase shift of a periodically sent signal allows to estimate the distance between all devices in a network and a specific reference device. This approach significantly reduces the communication overhead leading to a more resource-efficient operation of the communication module and, thus, potentially extending the lifetime of the mobile devices. Experiments demonstrate that a network with an average of ten devices within communication range can be synchronized using a firefly-inspired decentralized synchronization algorithm. Also, we show that the resulting distance estimates have a higher accuracy compared to the results of an algorithm which is based on asynchronous exchange of messages.

In service-oriented environments (e.g. Cloud Computing or Utility Computing), automated service discovery is crucial to enable self-organizing technical components that are able to discover and consume services autonomously. To this end, precise and robust service discovery algorithms are desirable. In this paper, we propose an approach combining both syntactic and semantic search to increase accuracy of discovery results. Evaluation in an SOA simulation environment shows promising improvements in contrast to traditional centralized discovery approaches, such as UDDI.

Learning classifier systems (LCSs) are rule-based evolutionary reinforcement learning systems. Today, especially variants of Wilson's extended classifier system (XCS) are widely applied for machine learning. Despite their widespread application, LCSs have drawbacks, e. g., in multi-learner scennarios, since the Markov property is not fulfilled.

Due to steadily increasing mobility and the resulting rising traffic demands, serious congestion problems can be observed in many cities. One promising approach to alleviate the congestion effects is the coordination of the network's traffic signals in response to the traffic flow. The recently introduced Decentralised Progressive Signal Systems approach is an adaptive coordination mechanism for traffic signals in urban road networks that relies on local traffic data only. Since the decentralised process cannot lead to optimal results in some special cases, it is extended with an optional hierarchical component introduced in this paper. Based on a broader view on the current network traffic, this Regional Manager is responsible for determining which intersections are coordinated. The efficiency of the coordination determined by the Regional Manager is demonstrated in a simulation-based evaluation that considers the decentralised mechanism and an uncoordinated system for comparison.

Automated end-to-end Service Level Management (SLM) is crucial to enable self-organising Service-Oriented Architectures (SOA). In this paper, we present an approach based on Organic Computing to enable automated SLM by using automated service level negotiation. The evaluation results in a simulated SOA environment are presented to show the applicability of our approach.

Organic Computing (OC) and other research initiatives like Autonomic Computing or Proactive Computing have developed the vision of systems possessing life-like properties: they self-organize, adapt to their dynamically changing environments, and establish other so-called self-x properties, like self-healing, self-configuration, self-optimization, etc. What we are searching for in OC are methodologies and concepts for systems that allow to cope with increasingly complex networked application systems by introduction of self-x properties and at the same time guarantee a trustworthy and adaptive response to externally provided system objectives and control actions. Therefore, in OC, we talk about controlled self-organization . Although the terms self-organization and adaptivity have been discussed for years, we miss a clear definition of self-organization in most publications, which have a technically motivated background. In this article, we briefly summarize the state of the art and suggest a characterization of (controlled) self-organization and adaptivity that is motivated by the main objectives of the OC initiative. We present a system classification of robust, adaptable, and adaptive systems and define a degree of autonomy to be able to quantify how autonomously a system is working. The degree of autonomy distinguishes and measures external control that is exerted directly by the user ( no autonomy ) from internal control of a system which might be fully controlled by an observer/controller architecture that is part of the system ( full autonomy ). The quantitative degree of autonomy provides the basis for characterizing the notion of controlled self-organization. Furthermore, we discuss several alternatives for the design of organic systems.

editorial Free AccessEditorial: Special issue on organic computing Authors: Rolf P. Würtz Ruhr-University Bochum Ruhr-University BochumView Profile , Kirstie L. Bellman The Aerospace Corporation The Aerospace CorporationView Profile , Hartmut Schmeck Karlsruhe Institute of Technology Karlsruhe Institute of TechnologyView Profile , Christian Igel Ruhr-University Bochum Ruhr-University BochumView Profile Authors Info & Claims ACM Transactions on Autonomous and Adaptive SystemsVolume 5Issue 3Article No.: 9pp 1–3https://doi.org/10.1145/1837909.1837910Published:30 September 2010Publication History 1citation369DownloadsMetricsTotal Citations1Total Downloads369Last 12 Months22Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The design paradigm service-orientation combines proven design elements from previous approaches with design elements from recent technology evolution. However, little work has investigated so far the complexity associated with service-oriented systems. This paper proposes a simulation-based approach to assess the influence of inherent system properties on overall system complexity. In addition, this work provides results of experiments in a simulated environment to support our approach.

In this paper, we study parallelization of multi-objective optimization algorithms on a set of heterogeneous resources based on the Master-Slave model. The Master-Slave model is known to be the simplest parallelization paradigm, where a master processor sends function evaluations to several slave processors. The critical issue when using the standard methods on heterogeneous resources is that in every iteration of the optimization, the master processor has to wait for all of the computing resources (including the slow ones) to deliver the evaluations. In this paper, we study a new algorithm where all of the available computing resources are efficiently utilized to perform the multi-objective optimization task independent of the speed (fast or slow) of the computing processors. For this we propose a hybrid method using Multi-objective Particle Swarm optimization and Binary search methods. The new algorithm has been tested on a scenario containing heterogeneous resources and the results show that not only does the new algorithm perform well for parallel resources, but also when compared to a normal serial run on one computer.

Organic computing (OC) and other research initiatives like autonomic computing or proactive computing have developed the idea of systems that possess life-like properties, that self-organise, that adapt to their dynamically changing environments, and that establish other so-called self-x properties, like self-healing, self-configuration, self-optimisation etc. What we are searching for in OC are not concepts for systems that simply self-organise, but systems that self-organise to achieve a well defined system goal. Therefore we talk in OC aboutcontrolledself-organisation. Although the term self-organisation has been discussed for years, we miss a clear definition of self-organisation in most publications, which have a technically motivated background. In this paper, we summarise the state of the art and introduce a definition of self-organisation that addresses the problem of designing self-organising technical systems, which is the main objective of the OC initiative.

Abstract. In recent years, a number of authors have successfully extended particle swarm optimization to problem domains with multiple objectives. This paper addresses the issue of parallelizing multi-objective particle swarms. We propose and empirically compare two parallel versions which differ in the way they divide the swarm into subswarms that can be processed independently on different processors. One of the variants works asynchronously and is thus particularly suitable for heterogeneous computer clusters as occurring e.g. in modern grid computing platforms. 1

In the past, the focus of the computer industry has been to improve hardware performance and add more and more features to the software. As a result, more and more appliances surrounding us are equipped with embedded computational power and wireless communication. As such, they become ever more flexible and multifunctional, and almost indispensable in daily life. On the other hand, the resulting systems become increasingly complex and unreliable, posing new challenges to designer and user. Organic Computing (OC) has the vision to address the challenges of complex distributed systems by making them more life-like (organic), i.e. endowing them with abilities such as self-organization, self-configuration, self-repair, or adaptation. The designer's task is simplified, because it is no longer necessary to exactly specify the low-level system behavior in all possible situations that might occur, but instead leaving the system with a certain degree of freedom which allows it to react in an intelligent way to new situations. Also, use ofsuch systems is simplified, as they can be controlled by setting few high-level goals, rather than having to manipulate many low-level parameters with unclear influence. In this paper, we give a general introduction to OC, and propose a generic observer-controller architecture as a framework for designing OC systems. Then, it is shown how to use this architecture at the example of a traffic light controller. The paper concludes with a summary and a discussion of future challenges.

Organic computing is becoming the new vision for the design of complex systems, satisfying human needs for trustworthy systems that behave life-like by adapting autonomously to dynamic changes of the environment, and have self-x properties as postulated for autonomic computing. Organic computing is a response to the threatening view of being surrounded by interacting and self-organizing systems which may become unmanageable, showing undesired emergent behavior. Major challenges for organic system design arise from the conflicting requirements to have systems that are at the same time robust and adaptive, having sufficient degrees of freedom for showing self-x properties but being open for human intervention and operating with respect to appropriate rules and constraints to prevent the occurrence of undesired emergent behavior.

Evolutionary multi-objective optimization (EMO) may be computationally quite demanding, because instead of searching for a single optimum, one generally wishes to find the whole front of Pareto-optimal solutions. For that reason, parallelizing EMO is an important issue. Since we are looking for a number of Pareto-optimal solutions with different tradeoffs between the objectives, it seems natural to assign different parts of the search space to different processors. We propose the idea of cone separation which is used to divide up the search space by adding explicit constraints for each process. We show that the approach is more efficient than simple parallelization schemes, and that it also works on problems with a non-convex Pareto-optimal front.

We propose to modify a type of ant algorithm called Population based Ant Colony Optimization (P-ACO) to allow implementation on an FPGA architecture. Ant algorithms are adapted from the natural behavior of ants and used to find good solutions to combinatorial optimization problems. General layout on the FPGA and algorithmic description are covered The most notable achievements featured in this paper are a runtime reduction and including the approximation of the heuristic function by a small set of favored decisions which changes over time.

An ant colony optimization (ACO) approach for the resource-constrained project scheduling problem (RCPSP) is presented. Several new features that are interesting for ACO in general are proposed and evaluated. In particular, the use of a combination of two pheromone evaluation methods by the ants to find new solutions, a change of the influence of the heuristic on the decisions of the ants during the run of the algorithm, and the option that an elitist ant forgets the best-found solution are studied. We tested the ACO algorithm on a set of large benchmark problems from the Project Scheduling Library. Compared to several other heuristics for the RCPSP, including genetic algorithms, simulated annealing, tabu search, and different sampling methods, our algorithm performed best on average. For nearly one-third of all benchmark problems, which were not known to be solved optimally before, the algorithm was able to find new best solutions.

In this paper a formal model for asynchronous systems behaviour is presented which is suited for representing all levels of abstraction appearing in the design process. Based on a structural abstraction of asynchronous computation systems called asynchronous nets the behaviour of an asynchronous system can be represented by a set of so called abstract computations. It is shown how basic properties of such systems, and in particular, delay-insensitive behaviour, could be determined by investigating properties of abstract computations. Finally, it is demonstrated that the model enables formal verification of asynchronous systems over different levels of abstraction.

The heart of a massively parallel computer is its interconnection network. In this article we present a reconfigurable multiple bas network to support circuit switching as means of communication between processors of a multiprocessor machine. The main contribution of the papers is in demonstrating the simplicity of the routing hardware whilst still providing modularity and full utilization of the multiple bus system. A comparison with major interconnection network is also presented.

The time complexity of Thompson and Kung's (1977) s/sup 2/-way merge sort is analyzed and shown to be asymptotically optimal with respect to the recently improved lower bound on sorting on a mesh-connected n*n array. New lower bounds for systolic sorting are derived. A systolic version of s/sup 2/-way merge sort is systematically constructed and shown to be asymptotically optimal as well.>

A parallel algorithm for sorting n data items in O(n) steps is presented. Its simple structure and the fact that it needs local communication only make it suitable for an implementation in VLSI technology. The algorithm is based on a merge algorithm that merges four subfiles stored in a mesh-connected processor array. This merge algorithm is composed of the perfect shuffle and odd-even-transposition sort. For the VLSI implementation a systolic version of the algorithm is presented. The area and time complexities for a bit-serial and a bit-parallel version of this implementation are analyzed.