A single front genetic algorithm for parallel multi-objective optimization in dynamic environments

This paper proposes a new parallel evolutionary procedure to solve multi-objective dynamic optimization problems along with some measures to evaluate multi-objective optimization in dynamic environments. These dynamic optimization problems appear in quite different real-world applications with actual socio-economic relevance. In these applications, the objective functions, the constraints, and hence, also the solutions, can change over time and usually demand to be solved online whilst the size of the changes is unknown. Although parallel processing could be very useful in these problems to meet the solution quality requirements and constraints, to date, not many parallel approaches have been reported in the literature. Taking this into account, we introduce a multi-objective optimization procedure for dynamic problems that are based on PSFGA, a parallel evolutionary algorithm previously proposed by us for multi-objective optimization. It uses an island model where a process divides the population among the remaining processes and allows the communication and coordination among the subpopulations in the different islands. The proposed algorithm makes an exclusive use of non-dominating individuals for the selection and variation operator and applies a crowding mechanism to maintain the diversity and the distribution of the solutions in the Pareto front. We also propose a model to understand the benefits of parallel processing in multi-objective problems and the speedup figures obtained in our experiments.     

Suitability of genetic based exploration in the creative design process

Abstract

Finding creative solutions to design problems depends heavily on a fruitful exploration in early phases. Many aspects of evolutionary computation (EC) and in particular genetic algorithms (GA) make them highly suited as computational tools for discovering good solutions. This paper discusses specific aspects of the GA method which parallel traditional design methodologies described by creativity researchers including Gordon, deBono, Parnes, and Osborn among others. Because EC methods work with populations of ‘fairly good’ solutions, there is less danger that creativity will be harmed by design fixation, on one ‘best’ solution. An example application is demonstrated using the design of a small truss bridge. The solutions offered by the application are varied enough to allow the designer a choice of forms. At the same time, all of the solutions offered are ‘fairly good’. This demonstrates the aspects of EC which make it well suited for creative exploration of problems.     

A hybrid immigrants scheme for genetic algorithms in dynamic environments

Dynamic optimization problems are a kind of optimization problems that involve changes over time.They pose a serious challenge to traditional optimization methods as well as conventional genetic algorithms since the goal is no longer to search for the optimal solution(s) of a fixed problem but to track the moving optimum over time.Dynamic optimization problems have attracted a growing interest from the genetic algorithm community in recent years.Several approaches have been developed to enhance the performance of genetic algorithms in dynamic environments.One approach is to maintain the diversity of the population via random immigrants.This paper proposes a hybrid immigrants scheme that combines the concepts of elitism,dualism and random immigrants for genetic algorithms to address dynamic optimization problems.In this hybrid scheme,the best individual,i.e.,the elite,from the previous generation and its dual individual are retrieved as the bases to create immigrants via traditional mutation scheme.These elitism-based and dualism-based immigrants together with some random immigrants are substituted into the current population,replacing the worst individuals in the population.These three kinds of immigrants aim to address environmental changes of slight,medium and significant degrees respectively and hence efficiently adapt genetic algorithms to dynamic environments that are subject to different severities of changes.Based on a series of systematically constructed dynamic test problems,experiments are carried out to investigate the performance of genetic algorithms with the hybrid immigrants scheme and traditional random immigrants scheme.Experimental results validate the efficiency of the proposed hybrid immigrants scheme for improving the performance of genetic algorithms in dynamic environments.     

Exploiting characterization of dynamism for enhancing dynamic multi-objective evolutionary algorithms

Characterization of dynamism is an essential phase for some of the dynamic multi-objective evolutionary algorithms (DMOEAs) in order to improve their performance. Although frequency of change and severity of change are the two main perspectives of characterizing dynamic features of the dynamic multi-objective optimization problems (DMOPs), they do not sufficiently attract attentions of the research community. In this paper, we propose a set of new sensor-based change detection schemes for the DMOPs that significantly outperform the current used change detection schemes. Additionally, a new technique is proposed for detecting the change severity for DMOPs. The experimental evaluation based on different test problems and change severity levels validates performance of our technique. We also propose a novel adaptive algorithm called change-responsive NSGA-II (CR-NSGA-II) algorithm that incorporates the change detection schemes, the technique for change severity and a new response mechanism into the NSGA-II algorithm. Our algorithm demonstrates competitive and significantly better results than the leading DMOEAs on majority of test problems and metrics considered.     

A new population based adaptive domination change mechanism for diploid genetic algorithms in dynamic environments

In this paper, an adaptive domination change mechanism for diploid genetic algorithms with discrete representations is presented. It is aimed at improving the performance of existing diploid genetic algorithms in changing environments. Diploidy acts as a source of diversity in the gene pool while the adaptive domination mechanism guides the phenotype towards an optimum. The combined effect of diploidy and the adaptive domination forms a balance between exploration and exploitation. The dominance characteristic of each locus in the population is adapted through feedback from the ongoing search process. A dynamic bit matching benchmark is used to perform controlled experiments. Controlled changes to implement different levels of change severities and frequencies are used. The testing phase consists of four stages. In the first stage, the benefits of the adaptive domination mechanism are shown by testing it against previously proposed diploid approaches. In the second stage, the same adaptive approach is applied to a haploid genetic algorithm to show the effect of the diploidy on the performance of the proposed approach. In the third stage, the levels of diversity introduced by diploidy on the genotype and maintained by the adaptive domination mechanism on the phenotype are explored. In the fourth stage, tests are performed to examine the robustness of the chosen approaches against different mutation rates. Currently, the dominance change mechanism can be applied to di-allelic or multiallelic discrete representations and promising results are obtained as a result of the tests performed.

A network flow based approach for network selection in dynamic spectrum access networks

In this paper, we present a network flow based approach for dynamic network and channel selection for secondary users in dynamic spectrum access networks. Most approaches in the current literature on dynamic spectrum access networks do not consider dynamic network and channel selection. We present a network flow framework for network selection. We show that our approach can enable re-assignment of networks to secondary users and also re-assignment of channels to secondary users within the same network. The assignments and re-assignments take into account, the interference caused to primary users, the price each secondary user is willing to pay and the quality of service (QoS) obtained by each secondary user. We obtain a bound for the maximum number of re-assignments.     

A time-varying transfer function for balancing the exploration and exploitation ability of a binary PSO

Many real-world problems belong to the family of discrete optimization problems. Most of these problems are NP-hard and difficult to solve efficiently using classical linear and convex optimization methods. In addition, the computational difficulties of these optimization tasks increase rapidly with the increasing number of decision variables. A further difficulty can be also caused by the search space being intrinsically multimodal and non-convex. In such a case, it is more desirable to have an effective optimization method that can cope better with these problem characteristics. Binary particle swarm optimization (BPSO) is a simple and effective discrete optimization method. The original BPSO and its variants have been used to solve a number of classic discrete optimization problems. However, it is reported that the original BPSO and its variants are unable to provide satisfactory results due to the use of inappropriate transfer functions. More specifically, these transfer functions are unable to provide BPSO a good balance between exploration and exploitation in the search space, limiting their performances. To overcome this problem, this paper proposes to employ a time-varying transfer function in the BPSO, namely TV_T-BPSO. To understand the search behaviour of the TV_T-BPSO, we provide a systematic analysis of its exploration and exploitation capability. Our experimental results demonstrate that TV_T-BPSO outperforms existing BPSO variants on both low-dimensional and high-dimensional classical 0–1 knapsack problems, as well as a 200-member truss problem, suggesting that TV_T-BPSO is able to better scale to high dimensional combinatorial problems than the existing BPSO variants and other metaheuristic algorithms.     

A Two-Level Function Evaluation Management Model for Multi-Population Methods in Dynamic Environments: Hierarchical Learning Automata Approach

ABSTRACT

The fitness evaluation (FE) management has been successfully applied to improve the performance of multi-population methods for dynamic optimisation problems (DOPs). In this work, we extend one of its variants to address DOPs which was recently proposed by the authors. The aim of our proposal is to increase the efficiency of the FE management. To this end, we propose a technique based on hierarchical learning automata that manages FEs at two level: at first level the algorithm decides which population should be executed, and at the second level it specifies the operation that should be performed by the selected population. A detailed experimental analysis shows the effectiveness of our proposal.     

A sensor for dynamic tactile information with applications in human–robot interaction and object exploration

We present a novel tactile sensor, which is applied for dextrous grasping with a simple robot gripper. The hardware novelty consists of an array of capacitive sensors, which couple to the object by means of little brushes of fibers. These sensor elements are very sensitive (with a threshold of about 5 mN) but robust enough not to be damaged during grasping. They yield two types of dynamical tactile information corresponding roughly to two types of tactile sensor in the human skin. The complete sensor consists of a foil-based static force sensor, which yields the total force and the center of the two-dimensional force distribution and is surrounded by an array of the dynamical sensor elements. One such sensor has been mounted on each of the two gripper jaws of our humanoid robot and equipped with the necessary read-out electronics and a CAN bus interface. We describe applications to guiding a robot arm on a desired trajectory with negligible force, reflective grip improvement, and tactile exploration of objects to create a shape representation and find stable grips, which are applied autonomously on the basis of visual recognition.     

一种面向无线传感器网络协同任务分配的动态联盟更新机制

在面向目标追踪等应用的无线传感器网络研究中,协同任务分配机制的研究是很重要的.基于动态联盟机制的协同任务分配方法是事件触发的.适用于任务出现频率相对较低的大规模无线传感器网络.本文在基于动态联盟机制研究的基础上,首先引入了联盟覆盖范围和休眠盟员的概念,进一步消除针对同一任务的检测传感器节点的冗余,降低系统的能量消耗;而后又给出了一种动态联盟的更新机制,以保证动态联盟执行任务时的连续性,在一定程度上保证网络的检测性能.最后通过仿真,从系统总能耗、目标捕获率和检测误差标准差等方面检验了算法的性能,并给出了缓冲带宽度等参数对能耗和网络检测性能的影响.     

A multi-objective evolutionary method for learning granularities based on fuzzy discretization to improve the accuracy-complexity trade-off of fuzzy rule-based classification systems: D-MOFARC algorithm

Multi-objective evolutionary algorithms represent an effective tool to improve the accuracy-interpretability trade-off of fuzzy rule-based classification systems. To this aim, a tuning process and a rule selection process can be combined to obtain a set of solutions with different trade-offs between the accuracy and the compactness of models. Nevertheless, an initial model needs to be defined, in particular the parameters that describe the partitions and the number of fuzzy sets of each variable (i.e. the granularities) must be determined. The simplest approach is to use a previously established single granularity and a uniform fuzzy partition for each variable. A better approach consists in automatically identifying from data the appropriate granularities and fuzzy partitions, since this usually leads to more accurate models.This contribution presents a fuzzy discretization approach, which is used to generate automatically promising granularities and their associated fuzzy partitions. This mechanism is integrated within a Multi-Objective Fuzzy Association Rule-Based Classification method, namely D-MOFARC, which concurrently performs a tuning and a rule selection process on an initial knowledge base. The aim is to obtain fuzzy rule-based classification systems with high classification performances, while preserving their complexity.     

Incorporating sustainable criteria in a dynamic multi-objective recommendation planning tool for a continuous manufacturing process: A dairy case study

The activity of scheduling the production plan with the aim of achieving an optimal criterion has been explored in literature for several manufacturing sectors, in particular when it comes to solving scheduling NP-complete problems. In Dairy Manufacturing, determining an optimum criterion for the scheduling process has numerous internal and external challenges due to the complexity of this environment.The initial stages in the Dairy process are characterised by a continuous manufacturing environment and specific operational issues are observable: interruptions for the accomplishment of Cleaning-In-Place (CIP); a short raw material lifespan which demands a fast processing rate; and the stochastic raw material supply variation. By highlighting these three aspects, a critical trade-off emerges: CIP cycle-times heavily reduce the processing capacity, whereas the raw material processed requires an increase in available capacity due to the impact of seasonality, perishability and stochastic deliveries. Therefore, the scheduling plan must be dynamically readapted based on the current inventory, volume and frequency supplied, CIP cycle-times, maximum equipment running hours and downstream capacities.The aim of this research is to develop an integrated approach for generating equipment schedules under supply uncertainty typically observed in the dairy sector where criteria of sustainability are effortlessly incorporated for an improved decision-making process. An efficient Multi-objective Algorithm (MOA) combining conflicting key performance metrics such as minimising Work-In-Process (WIP), maximising Service Level Agreement (SLA), Utilisation and Energy consumption is proposed.The novelty consists of the ability to dynamically select trade-off criteria and visualise the optimum production plan according to the conditions defined by the decision-maker. The appropriate schedules are presented in a Pareto Frontier graph highlighting the entire non-dominance region according to the volume and frequency supplied. Even though sustainability metrics are usually ignored during production plan definitions, namely when a weak correlation between both environmental and profitable criteria is identified, the results demonstrate improved performance when both sustainable approaches are well explored.     

A virtual centrifugal force based navigation algorithm for explorative robotic tasks in unknown environments

In many robotic tasks, there is no a priori knowledge of the environment. This makes it necessary for robots to explore the environment. Navigation algorithms for robots to map the environment completely in a short time play a very important role in the robotic task completion. A navigation algorithm based on virtual centrifugal force is proposed to complete the robotic exploration of the unknown environment using rang sensors in this paper. Collisions between a robot and an obstacle or between robots can be avoided with the application of the proposed navigation rules. The kinematics and dynamics equations of robots adopting the algorithm are also given. The simulation experiments demonstrate the operation of the algorithm. Several simulation experiments of various representative robotic tasks are carried out, based on the explorative navigation algorithm, which successfully validate the virtual centrifugal force based navigation algorithm.     

A novel hybrid adaptive collaborative approach based on particle swarm optimization and local search for dynamic optimization problems

This paper proposes a novel hybrid approach based on particle swarm optimization and local search, named PSOLS, for dynamic optimization problems. In the proposed approach, a swarm of particles with fuzzy social-only model is frequently applied to estimate the location of the peaks in the problem landscape. Upon convergence of the swarm to previously undetected positions in the search space, a local search agent (LSA) is created to exploit the respective region. Moreover, a density control mechanism is introduced to prevent too many LSAs crowding in the search space. Three adaptations to the basic approach are then proposed to manage the function evaluations in the way that are mostly allocated to the most promising areas of the search space. The first adapted algorithm, called HPSOLS, is aimed at improving PSOLS by stopping the local search in LSAs that are not contributing much to the search process. The second adapted, algorithm called CPSOLS, is a competitive algorithm which allocates extra function evaluations to the best performing LSA. The third adapted algorithm, called CHPSOLS, combines the fundamental ideas of HPSOLS and CPSOLS in a single algorithm. An extensive set of experiments is conducted on a variety of dynamic environments, generated by the moving peaks benchmark, to evaluate the performance of the proposed approach. Results are also compared with those of other state-of-the-art algorithms from the literature. The experimental results indicate the superiority of the proposed approach.     

A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests

Combinatorial optimization problems are usually modeled in a static fashion. In this kind of problems, all data are known in advance, i.e. before the optimization process has started. However, in practice, many problems are dynamic, and change while the optimization is in progress. For example, in the dynamic vehicle routing problem (DVRP), new orders arrive when the working day plan is in progress. In this case, routes must be reconfigured dynamically while executing the current simulation. The DVRP is an extension of a conventional routing problem, its main interest being the connection to many real word applications (repair services, courier mail services, dial-a-ride services, etc.). In this article, a DVRP is examined, and solving methods based on particle swarm optimization and variable neighborhood search paradigms are proposed. The performance of both approaches is evaluated using a new set of benchmarks that we introduce here as well as existing benchmarks in the literature. Finally, we measure the behavior of both methods in terms of dynamic adaptation.