Sleep staging is critical for evaluating sleep quality and regulating sleep patterns. While deep learning has shown potential for automatically scoring sleep stages from raw signals, many existing models are overly complex, computationally intensive, and rely on future information, limiting their use in real-time monitoring and widespread applications. To address these challenges, we propose EfficientSleepNet, a lightweight architecture for sleep staging based on single-channel EEG. EfficientSleepNet integrates depthwise separable convolutions, grouped convolutions, channel reordering, and a novel channel attention mechanism. Compared to previous models, EfficientSleepNet significantly reduces both parameter count and complexity. We conducted extensive evaluations on two public datasets, SleepEDF-20 and SleepEDF-78, achieving accuracies of 84.4% and 80.8%, respectively, with only 83.8K parameters. These findings demonstrate that EfficientSleepNet substantially reduces model complexity and parameter count, offering strong potential for real-time sleep staging applications.

In a data center, deploying a microservice-based SaaS will result in a spike in energy usage, since the computation servers where the microservices are deployed will consume more energy as a result of an increase in computation workload. The data center's communications network will also consume more energy due to the increased communication among the microservices of the SaaS. Due to the fact that microservice-based SaaS deployment is handled by the developer of the microservice-based SaaS and can only be deployed on virtual machines rented by the developer, this issue cannot be taken into account in traditional microservice-based SaaS deployment methods. In this paper, a new microservice-based SaaS deployment method is proposed. The new approach relies on the data center determining where microservices should be deployed. The new microservice-based SaaS deployment method considers the energy increase in the computation servers and in the communication network. The microservice-based SaaS deployment problem is a combinatorial optimization problem. Thus, a genetic algorithm with repairing mechanism is proposed to solve the problem. Compared to traditional deployment approach, the proposed method is capable of reducing the energy consumption associated with microservice-based SaaS deployment by 37.55%.

The use of cloud services to process a large amount of data is growing and demands for scalable, reliable, and highly available services in cloud environments are raising. The demands and the urge for developing these facilities have made parallel computing more appealing. Cloud providers offer various types of Virtual Machines (VMs) that are compatible with parallel processing and the clients should pay for their hourly usage. The price varies based on the type, the number and the hiring time of the VMs. A daily price fluctuation timetable has been proposed and scaling the number of VMs on that helps to schedule the computations to meet both deadline and cost minimization goals. It becomes critical to select appropriate VMs and distribute workload efficiently across them. Therefore, the computations and the VMs require being well-managed, scheduled and monitored to meet the deadline while minimizing the total hiring cost. To address these concerns, this paper formulated the problem to calculate the total hiring cost before and during the computations. The execution time and the total cost are calculated based on the application's input size and the required type and the number of VMs. We worked on two applications as sample benchmarks to identify the best approach to choose and manage the VMs to compute them. Our results indicate that among different available approaches for hiring VMs, identifying the most affordable approach leads to minimizing the cost signiflcantly.

Different sound events have different time-frequency scale characteristics, which are useful for sound event detection (SED), but not yet effectively exploited. In this paper, we aim to adaptively select multi-scale feature information that is conducive to classification of sound events. We propose a novel module, namely multi-scale residual attention (MSRA), which is composed of multi-scale residual convolutional block and selective multiscale attention block. Multi-scale residual convolution block extracts features at multiple scales, among which selective multiscale attention block adaptively selects the features that are helpful for event classification. Experimental results prove that our method outperforms the state-of-the-art model by 3.7% on Task 4 of the DCASE 2018 Challenge dataset.

MapReduce is a major computing model for big data solutions through distributed virtual computing environment. Cloud container environment is one of the platforms to compute MapReduce tasks. However, a new challenge lies on the lack of resource provisioning for containerized MapReduce computations with deadline requirements. There are two major resource provisioning strategies to solve this challenge: static and dynamic, but neither of them can satisfactorily solve it. This paper presents a resource provisioning framework, integrating semi-static and dynamic strategies, to address this challenge. The framework includes a performance model to estimate minimum resource requirements under deadline limitation, and a scheduler to adjust resource allocation. Experimental results show that the proposed semi-static framework can complete the MapReduce computation with less resource utilization and meeting the given deadline. However, proposed dynamic resource provisioning is not suitable for our scenario caused by resource overhead and late completion.

Knowledge Graphs (KGs) have been proven to be incredibly useful for enriching semantic Web search results and allowing queries with a well-defined result set. In recent years much attention has been given to the task of inferring missing facts based on existing facts in a KG. Approaches have also been proposed for inferring types of entities, however these are successful in common types such as 'Person', 'Movie', or 'Actor'. There is still a large gap, however, in the inference of fine-grained types which are highly important for exploring specific lists and collections within web search. Generally there are also relatively fewer observed instances of fine-grained types present to train in KGs, and this poses challenges for the development of effective approaches. In order to address the issue, this paper proposes a new approach to the fine-grained type inference problem. This new approach is explicitly modeled for leveraging domain knowledge and utilizing additional data outside KG, that improves performance in fine-grained type inference. Further improvements in efficiency are achieved by extending the model to probabilistic inference based on entity similarity and typed class classification. We conduct extensive experiments on type triple classification and entity prediction tasks on Freebase FB15K benchmark dataset. The experiment results show that the proposed model outperforms the state-of-the-art approaches for type inference in KG, and achieves high performance results in many-to-one relation in predicting tail for KG completion task.

Energy efficiency is a critical issue in the management and operation of data centers, which form the backbone of cloud computing. Virtual machine (VM) placement has a significant impact on energy efficiency improvement for data centers. Among various methods to solve the VM placement problem, genetic algorithm (GA) has been well accepted for its quality of solutions. However, GA is also computationally demanding, particularly in its fitness, limiting further improvement in energy efficiency of data centers in the scenarios where a fast solution is required. To address this issue, this paper formulates the VM placement problem for energy efficiency as a constrained optimization problem. Then, employing GA to solve the optimization, it presents an approach for efficient computation of GA fitness function. The improved computational efficiency is achieved through a new data structure design, which reduces the complexity of the computation from quadratic to linear, to the input size of the problem. Experimental studies show a huge computation time saving from our approach over the existing technique, which is basically Brute-force.

Embedded streaming applications are facing increasingly demanding performance requirements in terms of throughput. A common mechanism for providing high compute power with a low energy budget is to use a very large number of low-power cores, often in the form of a Massively Parallel System on Chip (MPSoC). The challenge with programming such massively parallel systems is deciding how to optimally map the computation to individual cores for maximizing throughput. In this work we present an automatic parallelizing compiler for the StreamIt programming language that efficiently and effectively maps computation to individual cores. The compiler must be both effective, meaning that it does a good job of optimizing for throughput; but also efficient, in that the time taken to find such a mapping must scale well as the number of cores and size of the Stream program increases. We improve on previous work that used Integer Linear Programming (ILP) to map StreamIT programs to multicore systems by formulating the mapping problem in a different way using mostly real rather than integer variables. Using so called Mixed Integer Linear Programming (MILP) dramatically reduces the cost compared to standard ILP. This alternative formulation creates what we call an optimistic solution that we then need to adjust slightly to obtain a final feasible solution. We show that this new approach is always close, if not better in terms of effectiveness, while being dramatically better in terms of scalability and efficiency.

Quality of Service (QoS) is a new issue in cloud-based MapReduce, which is a popular computation model for parallel and distributed processing of big data. QoS guarantee is challenging in a dynamical computation environment due to the fact that a fixed resource allocation may become under-provisioning, which leads to QoS violation, or over-provisioning, which increases unnecessary resource cost. This requires runtime resource scaling to adapt environmental changes for QoS guarantee. Aiming to guarantee the QoS, which is referred as to hard deadline in this work, this paper develops a theory to determine how and when resource is scaled up/down for cloud-based MapReduce. The theory employs a nonlinear transformation to define the problem in a reverse resource space, simplifying the theoretical analysis significantly. Then, theoretical results are presented in three theorems on sufficient conditions for guaranteeing the QoS of cloud-based MapReduce. The superiority and applications of the theory are demonstrated through case studies.

The dramatically increasing energy consumption of data centers is an important issue and one of the most efficient ways to tackle the issue is through server consolidation. The basic idea of server consolidation is to move all virtual machines (VMs) to as few energy efficient servers as possible, and then switch off unused servers. Many efficient server consolidation approaches have been proposed and one of the most efficient approaches is to use a Genetic Algorithm (GA) to find an optimal or near-optimal solution to the server consolidation problem. Aiming at reducing the computation time and the number of VM migrations incurred by server consolidation, this paper proposes a Decrease- and-Conquer Genetic Algorithm (DCGA). This DCGA adopts a decrease-and-conquer strategy to decrease the problem size and to decrease the number of VM migrations without significantly compromising the quality of solutions. The DCGA is compared with a classical GA and the most popular approach, namely FFD, for the server consolidation problem by experiments and the experimental results show that the DCGA can find a solution very close to the solution generated by the classical GA with much shorter computation time and incur much less VM migrations for all the test problems, and that the DCGA can generate a much better solution than the FFD.

Guaranteeing quality of service (QoS) with minimum computation cost is the most important objective of cloud-based MapReduce computations. Minimizing the total computation cost of cloud-based MapReduce computations is done through MapReduce placement optimization. MapReduce placement optimization approaches can be classified into two categories: homogeneous MapReduce placement optimization and heterogeneous MapReduce placement optimization. It is generally believed that heterogeneous MapReduce placement optimization is more effective than homogeneous MapReduce placement optimization in reducing the total running cost of cloud-based MapReduce computations. This paper proposes a new approach to the heterogeneous MapReduce placement optimization problem. In this new approach, the heterogeneous MapReduce placement optimization problem is transformed into a constrained combinatorial optimization problem and is solved by an innovative constructive algorithm. Experimental results show that the running cost of the cloud-based MapReduce computation platform using this new approach is 24.3-44.0 percent lower than that using the most popular homogeneous MapReduce placement approach, and 2.0-36.2 percent lower than that using the heterogeneous MapReduce placement approach not considering the spare resources from the existing MapReduce computations. The experimental results have also demonstrated the good scalability of this new approach.

Network real-time kinematic (NRTK) is a technology that can provide centimeter-level accuracy positioning services in real-time, and it is enabled by a network of continuously operating reference stations (CORS). The location-oriented CORS placement problem is an important problem in the design of a NRTK as it will directly affect not only the installation and operational cost of the NRTK, but also the quality of positioning services provided by the NRTK. This paper presents a memetic algorithm (MA) for the location-oriented CORS placement problem, which hybridizes the powerful explorative search capacity of a genetic algorithm and the efficient and effective exploitative search capacity of a local optimization. Experimental results have shown that the MA has better performance than existing approaches. In this paper, we also conduct an empirical study about the scalability of the MA, effectiveness of the hybridization technique and selection of crossover operator in the MA.

This paper provides a three-layered framework to monitor the positioning performance requirements of real-time relative positioning (RRP) systems of the Cooperative Intelligent Transport Systems that support cooperative collision warning (CCW) applications. These applications exploit state data of surrounding vehicles obtained solely from the Global Positioning System (GPS) and dedicated short-range communications (DSRC) units without using other sensors. To this end, this paper argues the need for the GPS/DSRC-based RRP systems to have an autonomous monitoring mechanism, since the operation of CCW applications is meant to augment safety on roads. The advantages of autonomous integrity monitoring are essential and integral to any safety-of-life system. The autonomous integrity monitoring framework proposed necessitates the RRP systems to detect/predict the unavailability of their subsystems and of the integrity monitoring module itself and, if available, to account for effects of data link delays and breakages of DSRC links, as well as of faulty measurement sources of GPS and/or integrated augmentation positioning systems, before the information used for safety warnings/alarms becomes unavailable, unreliable, inaccurate, or misleading. Hence, a monitoring framework using a tight integration and correlation approach is proposed for instantaneous reliability assessment of the RRP systems. Ultimately, using the proposed framework, the RRP systems will provide timely alerts to users when the RRP solutions cannot be trusted or used for the intended operation.

The placement of the mappers and reducers on the machines directly affects the performance and cost of the MapReduce computation in cloud computing. From the computational point of view, the mappers/reducers placement problem is a generalization of the classical bin packing problem, which is NP-complete. Thus, in this paper we propose a new heuristic algorithm for the mappers/reducers placement problem in cloud computing and evaluate it by comparing with some other heuristics on solution quality and computation time by solving a set of test problems with various characteristics. The computational results show that our heuristic algorithm is much more efficient than the other heuristics. Also, we verify the effectiveness of our heuristic algorithm by comparing the mapper/reducer placement for a benchmark problem generated by our heuristic algorithm with a conventional mapper/reducer placement. The comparison results show that the computation using our mapper/reducer placement is much cheaper while still satisfying the computation deadline.

MapReduce is a computation model for processing large data sets in parallel on large clusters of machines, in a reliable, fault-tolerant manner. A MapReduce computation is broken down into a number of map tasks and reduce tasks, which are performed by so called mappers and reducers, respectively. The placement of the mappers and reducers on the machines directly affects the performance and cost of the MapReduce computation. From the computational point of view, the mappers/reducers placement problem is a generation of the classical bin packing problem, which is NP-complete. Thus, in this paper we propose a new grouping genetic algorithm for the mappers/reducers placement problem in cloud computing. Compared with the original one, our grouping genetic algorithm uses an innovative coding scheme and also eliminates the inversion operator which is an essential operator in the original grouping genetic algorithm. The new grouping genetic algorithm is evaluated by experiments and the experimental results show that it is much more efficient than four popular algorithms for the problem, including the original grouping genetic algorithm.

A Software-as-a-Service or SaaS can be delivered in a composite form, consisting of a set of application and data components that work together to deliver higher-level functional software. Components in a composite SaaS may need to be scaled — replicated or deleted, to accommodate the user's load. It may not be necessary to replicate all components of the SaaS, as some components can be shared by other instances. On the other hand, when the load is low, some of the instances may need to be deleted to avoid resource underutilisation. Thus, it is important to determine which components are to be scaled such that the performance of the SaaS is still maintained. Extensive research on the SaaS resource management in Cloud has not yet addressed the challenges of scaling process for composite SaaS. Therefore, a hybrid genetic algorithm is proposed in which it utilises the problem's knowledge and explores the best combination of scaling plan for the components. Experimental results demonstrate that the proposed algorithm outperforms existing heuristic-based solutions.

In the past few years, there has been a steady increase in the attention, importance and focus of green initiatives related to data centers. While various energy aware measures have been developed for data centers, the requirement of improving the performance efficiency of application assignment at the same time has yet to be fulfilled. For instance, many energy aware measures applied to data centers maintain a trade-off between energy consumption and Quality of Service (QoS). To address this problem, this paper presents a novel concept of profiling to facilitate offline optimization for a deterministic application assignment to virtual machines. Then, a profile-based model is established for obtaining near-optimal allocations of applications to virtual machines with consideration of three major objectives: energy cost, CPU utilization efficiency and application completion time. From this model, a profile-based and scalable matching algorithm is developed to solve the profile-based model. The assignment efficiency of our algorithm is then compared with that of the Hungarian algorithm, which does not scale well though giving the optimal solution.

In the real world there are many problems in network of networks (NoNs) that can be abstracted to a so-called minimum interconnection cut problem, which is fundamentally different from those classical minimum cut problems in graph theory. Thus, it is desirable to propose an efficient and effective algorithm for the minimum interconnection cut problem. In this paper we formulate the problem in graph theory, transform it into a multi-objective and multi-constraint combinatorial optimization problem, and propose a hybrid genetic algorithm (HGA) for the problem. The HGA is a penalty-based genetic algorithm (GA) that incorporates an effective heuristic procedure to locally optimize the individuals in the population of the GA. The HGA has been implemented and evaluated by experiments. Experimental results have shown that the HGA is effective and efficient.

Software as a Service (SaaS) is gaining more and more attention from software users and providers recently. This has raised many new challenges to SaaS providers in providing better SaaSes that suit everyone needs at minimum costs. One of the emerging approaches in tackling this challenge is by delivering the SaaS as a composite SaaS. Delivering it in such an approach has a number of benefits, including flexible offering of the SaaS functions and decreased cost of subscription for users. However, this approach also introduces new problems for SaaS resource management in a Cloud data centre. We present the problem of composite SaaS resource management in Cloud data centre, specifically on its initial placement and resource optimization problems aiming at improving the SaaS performance based on its execution time as well as minimizing the resource usage. Our approach differs from existing literature because it addresses the problems resulting from composite SaaS characteristics, where we focus on the SaaS requirements, constraints and interdependencies. The problems are tackled using evolutionary algorithms. Experimental results demonstrate the efficiency and the scalability of the proposed algorithms.

Network RTK (Real-Time Kinematic) is a technology that is based on GPS (Global Positioning System) or more generally on GNSS (Global Navigation Satellite System) observations to achieve centimeter-level accuracy positioning in real time. It is enabled by a network of Continuously Operating Reference Stations (CORS). CORS placement is an important problem in the design of network RTK as it directly affects not only the installation and running costs of the network RTK, but also the Quality of Service (QoS) provided by the network RTK. In our preliminary research on the CORS placement, we proposed a polynomial heuristic algorithm for a so-called location-based CORS placement problem. From a computational point of view, the location-based CORS placement is a large-scale combinatorial optimization problem. Thus, although the heuristic algorithm is efficient in computation time it may not be able to find an optimal or near optimal solution. Aiming at improving the quality of solutions, this paper proposes a repairing genetic algorithm (RGA) for the location-based CORS placement problem. The RGA has been implemented and compared to the heuristic algorithm by experiments. Experimental results have shown that the RGA produces better quality of solutions than the heuristic algorithm.

Recently, Software as a Service (SaaS) in Cloud computing, has become more and more significant among software users and providers. To offer a SaaS with flexible functions at a low cost, SaaS providers have focused on the decomposition of the SaaS functionalities, or known as composite SaaS. This approach has introduced new challenges in SaaS resource management in data centres. One of the challenges is managing the resources allocated to the composite SaaS. Due to the dynamic environment of a Cloud data centre, resources that have been initially allocated to SaaS components may be overloaded or wasted. As such, reconfiguration for the components' placement is triggered to maintain the performance of the composite SaaS. However, existing approaches often ignore the communication or dependencies between SaaS components in their implementation. In a composite SaaS, it is important to include these elements, as they will directly affect the performance of the SaaS. This paper will propose a Grouping Genetic Algorithm (GGA) for multiple composite SaaS application component clustering in Cloud computing that will address this gap. To the best of our knowledge, this is the first attempt to handle multiple composite SaaS reconfiguration placement in a dynamic Cloud environment. The experimental results demonstrate the feasibility and the scalability of the GGA.

Improving energy efficiency has become increasingly important in data centers in recent years to reduce the rapidly growing tremendous amounts of electricity consumption. The power dissipation of the physical servers is the root cause of power usage of other systems, such as cooling systems. Many efforts have been made to make data centers more energy efficient. One of them is to minimize the total power consumption of these servers in a data center through virtual machine consolidation, which is implemented by virtual machine placement. The placement problem is often modeled as a bin packing problem. Due to the NP-hard nature of the problem, heuristic solutions such as First Fit and Best Fit algorithms have been often used and have generally good results. However, their performance leaves room for further improvement. In this paper we propose a Simulated Annealing based algorithm, which aims at further improvement from any feasible placement. This is the first published attempt of using SA to solve the VM placement problem to optimize the power consumption. Experimental results show that this SA algorithm can generate better results, saving up to 25 percentage more energy than First Fit Decreasing in an acceptable time frame.

Software as a Service (SaaS) in Cloud is getting more and more significant among software users and providers recently. A SaaS that is delivered as composite application has many benefits including reduced delivery costs, flexible offers of the SaaS functions and decreased subscription cost for users. However, this approach has introduced a new problem in managing the resources allocated to the composite SaaS. The resource allocation that has been done at the initial stage may be overloaded or wasted due to the dynamic environment of a Cloud. A typical data center resource management usually triggers a placement reconfiguration for the SaaS in order to maintain its performance as well as to minimize the resource used. Existing approaches for this problem often ignore the underlying dependencies between SaaS components. In addition, the reconfiguration also has to comply with SaaS constraints in terms of its resource requirements, placement requirement as well as its SLA. To tackle the problem, this paper proposes a penalty-based Grouping Genetic Algorithm for multiple composite SaaS components clustering in Cloud. The main objective is to minimize the resource used by the SaaS by clustering its component without violating any constraint. Experimental results demonstrate the feasibility and the scalability of the proposed algorithm.

Recognizing the impact of reconfiguration on the QoS of running systems is especially necessary for choosing an appropriate approach to dealing with dynamic evolution of mission-critical or non-stop business systems. The rationale is that the impaired QoS caused by inappropriate use of dynamic approaches is unacceptable for such running systems. To predict in advance the impact, the challenge is two-fold. First, a unified benchmark is necessary to expose QoS problems of existing dynamic approaches. Second, an abstract representation is necessary to provide a basis for modeling and comparing the QoS of existing and new dynamic reconfiguration approaches. Our previous work [8] has successfully evaluated the QoS assurance capabilities of existing dynamic approaches and provided guidance of appropriate use of particular approaches. This paper reinvestigates our evaluations, extending them into concurrent and parallel environments by abstracting hardware and software conditions to design an evaluation context. We report the new evaluation results and conclude with updated impact analysis and guidance.

Current research in secure messaging for Vehicular Ad hoc Networks (VANETs) focuses on employing a digital certificate-based Public Key Cryptosystem (PKC) to support security. However, the security overhead of such a scheme creates a transmission delay and introduces a time-consuming verification process to VANET communications. This paper proposes a non-certificate-based public key management for VANETs. A comprehensive evaluation of performance and scalability of the proposed public key management regime is presented, which is compared with a certificate-based PKC by employing a number of quantified analyses and simulations. In this paper, the authors demonstrate that the proposal can maintain security and assert that it can improve overall performance and scalability at a lower cost, compared with certificate-based PKC. The proposed scheme adds a new dimension to key management and verification services for VANETs.

Web service composition is an important problem in web service based systems. It is about how to build a new value-added web service using existing web services. A web service may have many implementations, all of which have the same functionality, but may have different QoS values. Thus, a significant research problem in web service composition is how to select a web service implementation for each of the web services such that the composite web service gives the best overall performance. This is so-called optimal web service selection problem. There may be mutual constraints between some web service implementations. Sometimes when an implementation is selected for one web service, a particular implementation for another web service must be selected. This is so called dependency constraint. Sometimes when an implementation for one web service is selected, a set of implementations for another web service must be excluded in the web service composition. This is so called conflict constraint. Thus, the optimal web service selection is a typical constrained combinatorial optimization problem from the computational point of view. This paper proposes a new hybrid genetic algorithm for the optimal web service selection problem. The hybrid genetic algorithm has been implemented and evaluated. The evaluation results have shown that the hybrid genetic algorithm outperforms other two existing genetic algorithms when the number of web services and the number of constraints are large.

Cloud computing is a latest new computing paradigm where applications, data and IT services are provided over the Internet. Cloud computing has become a main medium for Software as a Service (SaaS) providers to host their SaaS as it can provide the scalability a SaaS requires. The challenges in the composite SaaS placement process rely on several factors including the large size of the Cloud network, SaaS competing resource requirements, SaaS interactions between its components and SaaS interactions with its data components. However, existing applications' placement methods in data centres are not concerned with the placement of the component's data. In addition, a Cloud network is much larger than data center networks that have been discussed in existing studies. This paper proposes a penalty-based genetic algorithm (GA) to the composite SaaS placement problem in the Cloud. We believe this is the first attempt to the SaaS placement with its data in Cloud provider's servers. Experimental results demonstrate the feasibility and the scalability of the GA.

Vehicular ad hoc network (VANET) is a wireless ad hoc network that operates in a vehicular environment to provide communication between vehicles. VANET can be used by a diverse range of applications to improve road safety. Cooperative collision warning system (CCWS) is one of the safety applications that can provide situational awareness and warning to drivers by exchanging safety messages between cooperative vehicles. Currently, the routing strategies for safety message dissemination in CCWS are scoped broadcast. However, the broadcast schemes are not efficient as a warning message is sent to a large number of vehicles in the area, rather than only the endangered vehicles. They also cannot prioritize the receivers based on their critical time to avoid collision. This paper presents a more efficient multicast routing scheme that can reduce unnecessary transmissions and also use adaptive transmission range. The multicast scheme involves methods to identify an abnormal vehicle, the vehicles that may be endangered by the abnormal vehicle, and the latest time for each endangered vehicle to receive the warning message in order to avoid the danger. We transform this multicast routing problem into a delay-constrained minimum Steiner tree problem. Therefore, we can use existing algorithms to solve the problem. The advantages of our multicast routing scheme are mainly its potential to support various road traffic scenarios, to optimize the wireless channel utilization, and to prioritize the receivers.

We present a new penalty-based genetic algorithm for the multi-source and multi-sink minimum vertex cut problem, and illustrate the algorithm's usefulness with two real-world applications. It is proved in this paper that the genetic algorithm always produces a feasible solution by exploiting some domain-specific knowledge. The genetic algorithm has been implemented on the example applications and evaluated to show how well it scales as the problem size increases.

In the field of semantic grid, QoS-based Web service composition is an important problem. In semantic and service rich environment like semantic grid, the emergence of context constraints on Web services is very common making the composition consider not only QoS properties of Web services, but also inter service dependencies and conflicts which are formed due to the context constraints imposed on Web services. In this paper, we present a repair genetic algorithm, namely minimal-conflict hill-climbing repair genetic algorithm, to address the Web service composition optimization problem in the presence of domain constraints and inter service dependencies and conflicts. Experimental results demonstrate the scalability and effectiveness of the genetic algorithm.

Floorplanning is an important problem in Very Large- Scale Integrated-circuit (VLSI) design automation as it de- termines the performance, size, yield and reliability of VLSI chips. From the computational point of view, floorplan area minimization is an NP-hard problem. This paper presents a parallel genetic algorithm (GA) for floorplan area opti- mization. The parallel GA is based an island model with an asynchronous migration mechanism, and is implemented using Web services and multithreading technologies. The parallel GA is compared with a sequential GA that the par- allel GA is based on. Experimental results show that the parallel GA can produce better results than the sequential GA when they use the same amount of computing resources. In addition, since the number of islands and migration in- terval are two important parameters that directly affect the performance of island-based parallel GAs, the impact of the two parameters on the performance of the parallel GA are empirically studied in this paper.

Floorplanning is an important problem in very large scale integrated-circuit (VLSI) design automation as it determines the performance, size, yield, and reliability of VLSI chips. From the computational point of view, VLSI floorplanning is an NP-hard problem. In this paper, a memetic algorithm (MA) for a nonslicing and hard-module VLSI floorplanning problem is presented. This MA is a hybrid genetic algorithm that uses an effective genetic search method to explore the search space and an efficient local search method to exploit information in the search region. The exploration and exploitation are balanced by a novel bias search strategy. The MA has been implemented and tested on popular benchmark problems. Experimental results show that the MA can quickly produce optimal or nearly optimal solutions for all the tested benchmark problems.

Developing effective and efficient negotiation mechanisms for real-world applications such as e-business is challenging because negotiations in such a context are characterized by combinatorially complex negotiation spaces, tough deadlines, very limited information about the opponents, and volatile negotiator preferences. Accordingly, practical negotiation systems should be empowered by effective learning mechanisms to acquire dynamic domain knowledge from the possibly changing negotiation contexts. This article illustrates our adaptive negotiation agents, which are underpinned by robust evolutionary learning mechanisms to deal with complex and dynamic negotiation contexts. Our experimental results show that GA-based adaptive negotiation agents outperform a theoretically optimal negotiation mechanism that guarantees Pareto optimal. Our research work opens the door to the development of practical negotiation systems for real-world applications. © 2006 Wiley Periodicals, Inc. Int J Int Syst 21: 41–72, 2006.

Deciding the appropriate population size and number of is- lands for distributed island-model genetic algorithms is often critical to the algorithm’s success. This paper outlines a method that automatically searches for good combinations of island population sizes and the number of islands. The method is based on a race between competing parameter sets, and collaborative seeding of new parameter sets. This method is applicable to any problem, and makes distributed genetic algorithms easier to use by reducing the number of user-set parameters. The experimental results show that the proposed method robustly and reliably finds population and islands settings that are comparable to those found with traditional trial-and-error approaches.

Distributed Genetic Algorithms (DGAs) designed for the Internet have to take its high communication cost into consideration. For island model GAs, the migration topology has a major impact on DGA performance. This paper describes and evaluates an adaptive migration topology optimizer that keeps the communication load low while maintaining high solution quality. Experiments on benchmark problems show that the optimized topology outperforms static or random topologies of the same degree of connectivity. The applicability of the method on real-world problems is demonstrated on a hard optimization problem in VLSI design.

We describe and verify a convergence model that allows the islands in a parallel genetic algorithm to run at different speeds, and to simulate the effects of communication or machine failure. The model extends on present theory of parallel genetic algorithms and furthermore it provides insight into the design of asynchronous parallel genetic algorithms that work efficiently on volatile and heterogeneous networks, such as cycle-stealing applications working over the Internet. The model is adequate for comparing migration parameter settings in terms of convergence and fault tolerance, and a series of experiments show how the convergence is affected by varying the failure rate and the migration topology, migration rate, and migration interval. Experiments conducted show that while very sparse topologies are inefficient and failure-prone, even small increases in topology order result in more robust models with convergence rates that approach the ones found in fully-connected topologies.

Constrained via minimization is the problem of reassigning wire segments of a VLSI routing so that the number of vias is minimized. In this paper, a new approach is proposed for two-layer VLSI routing. This approach is able to handle any types of routing, and allows arbitrary number of wire segments split at a via candidate.