This paper presents a novel approach to addressing the long-sequence problem in high-resolution medical images for Vision Transformers (ViTs). Using smaller patches as tokens can enhance ViT performance, but quadratically increases computation and memory requirements. Therefore, the common practice for applying ViTs to high-resolution images is either to: (a) employ complex sub-quadratic attention schemes or (b) use large to medium-sized patches and rely on additional mechanisms within the model to capture the spatial hierarchy of details. We propose Symmetrical Hierarchical Forest (SHF), a lightweight approach that adaptively patches the input image to increase token information density and encode hierarchical spatial structures into the input embedding. We then apply a reverse depatching scheme to the output embeddings of the transformer encoder, eliminating the need for convolution-based decoders. Unlike previous methods that modify attention mechanisms \wahib{or use a complex hierarchy of interacting models}, SHF can be retrofitted to any ViT model to allow it to learn the hierarchical structure of details in high-resolution images without requiring architectural changes. Experimental results demonstrate significant gains in computational efficiency and performance: on the PAIP WSI dataset, we achieved a 3$\sim$32$\times$ speedup or a 2.95\% to 7.03\% increase in accuracy (measured by Dice score) at a $64K^2$ resolution with the same computational budget, compared to state-of-the-art production models. On the 3D medical datasets BTCV and KiTS, training was 6$\times$ faster, with accuracy gains of 6.93\% and 5.9\%, respectively, compared to models without SHF.

In this study, we propose a novel deep neural model, CWTLNet, specifically designed to address the unique characteristics of cryptocurrency trading, including significant short-term volatility, which operates around the clock, and is prone to sudden price jumps and drops. The architecture consists of two branches. The CWT branch employs a continuous wavelet transform (CWT) to extract time-frequency feature maps from the input time series. These feature maps are then processed by a stack of CWT Blocks, which are composed of residual structures with two Conv1D layers, allowing the model to capture local, ultra-short-term patterns in the data. The linear branch first decomposes the time series into its trend and residual components. Each component is modeled separately using linear models and subsequently recombined. The linear branch is particularly effective at capturing the periodic patterns embedded in the time series. Finally, the outputs of the two branches are fused through a gated mechanism with a temperature coefficient, enabling adaptive weighting of the branch outputs. Experimental results demonstrate that CWTLNet outperforms commonly used models — including LSTM, Transformer, and DLinear — on minute-level trading data for seven different cryptocurrencies. For example, The performance of CWTLNet on the Bitcoin dataset, in terms of Mean Squared Error (MSE) and Mean Absolute Error (MAE), shows improvements of at least 2.7% and 1.7%, respectively, compared to the aforementioned three models.

Overfitting is a well-documented and studied issue in supervised learning. Human experts have been designing methods to reduce over-fitting by observing the validation knowledge, e.g., learning rate schedules, dropout, and adversarial training. We propose a validation-loss landscape exploration/exploitation method called VKI (Validation Knowledge Inheritance). We reformulate the traditional gradient optimization problem as a reinforcement learning task to explore the validation-loss landscape. In particular, by treating the gradient descent process as a Markov Decision Process (MDP), where the validation losses are treated as the costs, we train a Q-network as a controller to learn the future rewards and later use it to decrease the validation loss of workers. We conduct the experiments in two reduced gradient action spaces on the MNIST, CIFAR-10, and CIFAR-100 datasets with naive dense neural networks and ResNet-56. Our results show that VKI could rediscover hyperparameters schedule rules and improve the models’ training and generalization by only exploring/exploiting the validation loss landscape, e.g., increasing the learning rate accelerated training and penalty factor when overfitting. In comparison to other metaHPO (Hyper Parameter Optimization) methods, we empirically show that VKI can leverage its weights-loss regression of Q-Net to enable the transfer to the target dataset without heavy retraining but with light fine-tuning.

Attention-based models are proliferating in the space of image analytics, including segmentation. The standard method of feeding images to transformer encoders is to divide the images into patches and then feed the patches to the model as a linear sequence of tokens. For high-resolution images, e.g. microscopic pathology images, the quadratic compute and memory cost prohibits the use of an attention-based model, if we are to use smaller patch sizes that are favorable in segmentation. The solution is to either use custom complex multi-resolution models or approximate attention schemes. We take inspiration from Adapative Mesh Refinement (AMR) methods in HPC by adaptively patching the images, as a pre-processing step, based on the image details to reduce the number of patches being fed to the model, by orders of magnitude. This method has a negligible overhead, and works seamlessly with any attention-based model, i.e. it is a pre-processing step that can be adopted by any attention-based model without friction. We demonstrate superior segmentation quality over SoTA segmentation models for real-world pathology datasets while gaining a geomean speedup of $6.9 \times$ for resolutions up to $64 K^{2}$, on up to 2,048 GPUs.

This paper proposes a novel decomposition method: Adjacent Intensity Matrix with Linkage Identification (AIM-LI) for large-scale optimization problems (LSOPs) in noisy environments. The most advanced differential grouping (DG)-based methods such as DG2, Recursive DG, and dual DG are environmentally sensitive, and the presence of noise may misguide these methods to identify the originally separable decision variables as non-separable. Although the noise may affect the absolute intensity of interactions, we can detect the intensity between separable and non-separable decision variables with potential relative differences. This difference can help us classify the separability. Based on this hypothesis, we define the interaction intensity of pairwise decision variables and save them to AIM. A significant intensity (SI) is selected from AIM to transform the AIM into the dependency structure matrix (DSM). To verify the feasibility of AIM-LI, we first run the pre-experiments and mathematically analyze the possibility of interaction identification in noisy environments. Furthermore, we implement a decomposition experiment on CEC2013 with different strengths of noise. Theoretical analysis and experimental results show that our proposal has great potential to detect and classify the separability of problems in noisy environments.

When training neural networks, the weights of the model are updated at each optimization step, and the older weights are discarded. In this paper, we propose a method called, Training Knowledge Inheritance (TKI), to use the knowledge about the progression of weight and loss data in reducing overfitting and improving the generalization in the later stages of training. We reformulate the traditional gradient optimization problem as a reinforcement learning task. In particular, by treating the trainable weight space as an environment, the learning rate as action, and the validation accuracies as the rewards, we train a Q-network (controller) to learn the discounted future validation accuracy and guide the later training of another network (worker). We conduct the experiments on the MNIST, CIFAR-10, and CIFAR-100 datasets with naive dense neural networks and ResNet-56. Our results show that TKI could rediscover learning rate schedule rules similar to previous works, including increasing, decaying, and cyclical repeating.

This contribution introduces a mixed-integer extension to the well-known Cassini1 space mission benchmark published by the European Space Agency (ESA). Due to it's highly nonlinear function properties, the Cassini1 benchmark is widely recognized by the evolutionary computing community as interesting test case. The Cassini1 benchmark implements a simplified model of an interplanetary space trajectory from Earth to Saturn, using four gravity-assist maneuvers (also known as fly-by's) at planets: Mercury, Mercury, Earth and Jupiter. Here the original continuous formulation of the Cassini1 benchmark is extended by four discrete (integer) variables, representing the choice of fly-by planets. Comprehensive numerical results investigate the complexity of this mixed-integer formulation and compare it with the purely continuous formulation. The results show that the difficulty to solve the mixed-integer formulation can significantly vary depending on small modifications of the integer search space. Preliminary multi-objective results are additionally presented in order to deepen the understanding of the observed mixed-integer performance.

We understand that many logical problems cannot be solved by using logic programs. Logic programs have the limited capability of representation. We try to overcome this limitation by adopting KR-logic, an extension to first-order logic. The extension includes function variables. In this paper, we take a problem which is well-described with function variables. We rely on Logical Problem Solving Framework (LPSF) to formalize our problem as a Model-intersection problem. Then we develop a solver for MI problems by adding five new transformation rules concerning function variables. Correctness of each rule is proved.i.e., each rule is an equivalent tranformation (ET) rule. Since each rule is correct, all ET rules can be used together without modification and combinational cost. Thus, the invented rules can be safely reused in other LPSF-based solvers.

Term rewriting is often used for proving theorems. To mechanizing such a proof method with computation correctness guaranteed strictly, we follow LPSF, which is a general framework for generating logical problem solution methods. In place of the first-order logic, we use KR-logic, which has function variables, for correct formalization. By repeating (1) specialization by a substitution for usual variables, and (2) application of an already derived rewriting rule, we can generate a term rewriting rule from the resulting equational clause. The obtained term rewriting rules are proved to be equivalent transformation rules. The correctness of the computation results is guaranteed. This theory shows that LPSF integrates logical inference and functional rewriting under the broader concept of equivalent transformation.

In this paper, we provide a novel framework to assess the vulnerability/robustness of a network with respect to pair-wise nodes' connectivity. In particular, we consider attackers that aim, at the same time, at dealing the maximum possible damage to the network in terms of the residual connectivity after the attack and at keeping the cost of the attack (e.g., the number of attacked nodes) at a minimum. Differently from the previous literature, we consider the attacker perspective using a multiobjective formulation and, rather than making hypotheses on the mindset of the attacker in terms of a particular tradeoff between the objectives, we consider the entire Pareto front of nondominated solutions. Based on that, we define novel global and local robustness/vulnerability indicators and we show that such indices can be the base for the implementation of effective protection strategies. Specifically, we propose two different problem formulations and we assess their performances. We conclude this paper by analyzing, as case studies, the IEEE118 power network and the U.S. Airline Network as it was in 1997, comparing the proposed approach against centrality measures.

This paper proposes a method for selecting optimal cloud resource configurations that satisfy hard and soft user constraints and multiple conflicting objectives. In the proposed method, feasible configurations generation and optimal configurations selection are carried out as two separate and independent processes that execute either sequentially or concurrently depending on the level of complexity of the optimization problem and the size of its solution space. The feasible configurations generation process utilizes an equivalent transformation-based constraint satisfaction method to generate the universe of feasible resource configurations that satisfy user requirements and constraints for a given cloud resource selection problem. In the optimal resource configurations selection process, nondominated sorting, reference points association, and niching/elitism are performed to produce a user-specified number of diverse Pareto-optimal configurations from the feasible resource configurations universe. The results of application of the proposed method to (1) a three-tier web application and (2) a cloud-based workflow resource allocation scenario verify its efficacy.

This paper proposes a new method that efficiently generates optimal and feasible cloud resource configurations for deploying genomic analytics applications. The proposed method generates optimal and feasible configurations with respect to system requirements by employing two different problem-solving techniques: an equivalent transformation algorithm and a multi-objective genetic algorithm. The equivalent transformation algorithm first generates feasible configurations through computation based on (1) state replacement of clause sets representing various resource configurations and (2) evaluation of their equivalence in terms of declarative meaning to the given requirements. Subsequently, the multi-objective genetic algorithm identifies the optimal configurations with respect to estimated financial cost and computational performance. The input to the proposed method is a logical formula describing the system requirements, whereas the output is a set of unit clauses representing Pareto-optimal and feasible cloud resource configurations for deploying a given genomic analytics application. The results of experiments conducted using a sample genomic analytics workflow and Amazon EC2 instances verify the efficacy of the proposed method.

Over the past decade, cloud computing has grown in popularity for the processing of scientific applications as a result of the scalability of the cloud and the ready availability of on-demand computing and storage resources. It is also a cost-effective alternative for scientific workflow executions with a pay-per-use paradigm. However, providing services with optimal performance at the lowest financial resource deployment cost is still challenging. Several fine-grained tasks are included in scientific workflow applications, and efficient execution of these tasks according to their processing dependency to minimize the overall makespan during workflow execution is an important research area. In this paper, a system for level-wise workflow makespan optimization and virtual machine deployment cost minimization for overall workflow optimization in cloud infrastructure is proposed. Further, balanced task clustering, to ensure load balancing in different virtual machine instances at each workflow level during workflow execution, is also considered. The system retrieves the necessary workflow information from a directed acyclic graph and uses the non-dominated sorting genetic algorithm II (NSGA-II) to carry out multiobjective optimization. Pareto front solutions obtained for makespan time and instance resource deployment cost for several scientific workflow applications verify the efficacy of our system.

We propose a Decomposition-based Multi-objective Evolutionary Algorithm (MOEA/D) that incorporates a linkage identification technique to enhance the ability to solve difficult multi-objective optimization problems that have complex interactions among genes. Ensuring tight linkages is essential for genetic recombination operators to work effectively by preserving building blocks. For problems which are difficult to ensure tight linkages in encoding, the dependencies among loci have to be analyzed to identify the linkages for each building block. The proposed MOEA/D employs Linkage Identification with non-Monotonicity Detection (LIMD) to identify the linkages among pairs of loci by checking the non-monotonicity of fitness differences caused by pairwise perturbations for each scalar function in the MOEA/D. The results of numerical experiments conducted using a difficult multi-objective test function in which each building block is loosely encoded over the strings indicate that the proposed MOEA/D-LIMD outperforms the original MOEA/D and MOEA/D with tree-based graphical model (MOEA/D-GM).

This paper proposes an intercloud brokerage method for system infrastructure deployments of genomic big data analytics workflows. The proposed method utilizes a conjunction of universally quantified atomic formula to describe requirements given by users, and selects combinations of cloud services based on logical reasoning by the replacement of definite clause sets created from conjunction of the atomic formulas, while preserving the declarative meaning of the system infrastructures' constraint conditions. We also define algorithms for the replacement of definite clause sets, and present an example of the use of the proposed intercloud brokerage method.

This contribution addresses the question if and how the impact of parallelization can influence the performance of an evolutionary algorithm on constrained mixed-integer nonlinear optimization problems. On a set of 200 MINLP benchmarks the performance of the MIDACO solver is numerically assessed with gradually increasing parallelization factor from 1 to 100. The results demonstrate that the efficiency of the algorithm can be significantly improved by parallelized function evaluation. Furthermore, the results indicate that the scale-up behaviour on the efficiency resembles a linear nature, which implies that this approach will even be promising for very large parallelization factors. The presented research is especially relevant to cpu-time consuming real-world applications, where only a low number of serial processed function evaluation can be calculated in reasonable time.

This paper proposes a 3D modeling system that uses multi-player interactive genetic algorithm (MiGA) to simplify the 3D modeling process for ordinary persons who wish to model pairs of glasses. The proposed system has three advantages: First, users are able to create 3D models via simple operations such as evaluation of 3D models. Second, this system reduces user fatigue by showing the information searched for and utilized by similar users, discovered by collaborative filtering. Third, this system also facilitates collaboration among a large number of users by employing Platform as-a Service (PaaS) and NoSQL database for scalability. The results of real and pseudo user experiments conducted verify the efficacy of the proposed system.

DDoS attacks become serious as one of the menaces of the Internet security. It is difficult to prevent because DDoS attacker send spoofing packets to victim which makes the identification of the origin of attacks very difficult. A series of techniques have been studied such as pattern matching by learning the attack pattern and abnormal traffic detection. However, pattern matching approach is not reliable because attackers always set attacks of different traffic patterns and pattern matching approach only learns from the past DDoS data. Therefore, a reliable system has to watch what kind of attacks are carried out now and investigate how to prevent those attacks. Moreover, the amount of traffic flowing through the Internet increase rapidly and thus packet analysis should be done within considerable amount of time. This paper proposes a scalable, real-time traffic pattern analysis based on genetic algorithm to detect and prevent DDoS attacks on Hadoop distributed processing infrastructure. Experimental results demonstrate the effectiveness of our scalable DDoS protection system.

The impact of parallelization on the optimization process of space mission trajectories is investigated in this contribution. As space mission trajectory reference model, the well known Cassini1 benchmark, published by the European Space Agency (ESA), is considered and solved here with the MIDACO optimization software. It can be shown that significant speed ups can be gained by applying parallelization.

This paper proposes a scalable framework to process and evolve services online adaptively from big data obtained from their users employing interactive evolutionary computation realized on a scalable infrastructure as platform as a service. Instead of collecting/storing/processing/analyzing big data to improve services offline, the proposed framework enables us to evolve and optimize adaptively every when collecting data from users interactively.

Two different parallelization strategies for evolutionary algorithms for mixed integer nonlinear programming (MINLP) are discussed and numerically compared in this contribution. The first strategy is to parallelize some internal parts of the evolutionary algorithm. The second strategy is to parallelize the MINLP function calls outside and independently of the evolutionary algorithm. The first strategy is represented here by a genetic algorithm (arGA) for numerical testing. The second strategy is represented by an ant colony optimization algorithm (MIDACO) for numerical testing. It can be shown that the first parallelization strategy represented by arGA is inferior to the serial version of MIDACO, even though if massive parallelization via GPGPU is used. In contrast to this, theoretical and practical tests demonstrate that the parallelization strategy of MIDACO is promising for cpu-time expensive MINLP problems, which often arise in real world applications.

Resource management in cloud platforms becomes an increasingly complex and daunting task surrounded by various challenges of stringent QoS requirements, service availability guaranteeing and escalating overhead of the infrastructure that resulted from operation costs and ecological impact. On the other hand, virtualization adds a greater flexibility to the resource managers in addressing such challenges. However, at the same time, it imposes a further challenge of added management complexity. Recently, we have proposed a resource management model for cloud platforms, which utilizes a new resource mapping formulation and relays on a hybrid virtualization framework in an attempt to realize a resource manager that intelligently adapts the available cloud resources to satisfy the conflicting objectives of the running applications and underlying infrastructures' requirements. Moreover, we have proposed state of the art Binary-Real coded Genetic Algorithm (BRGA), which has been applied successfully to a wide spectrum of global and constrained optimization problems from the known benchmark suites. In this paper, we aim to proceed by proposing a mathematical model and a modified version of BRGA to validate our model. In addition, we aim to evaluate the feasibility, effectiveness and scalability of our approach through simulation experiments.

Resource management in cloud platforms becomes an increasingly complex and daunting task surrounded by various challenges of stringent QoS requirements, service availability guaranteeing and escalating overhead of the infrastructure that resulted from operation costs and ecological effects. Virtualization adds a greater flexibility to the resource manager in addressing such challenges. However, it imposes a further challenge of added management complexity. So, in this brief paper, we attempt to address still an open question of how to employ virtualization techniques effectively to realize a resource manager that intelligently adapts cloud platforms resource usage to satisfy the conflicting objectives of running applications and underlying cloud infrastructures by proposing a novel multi-level architecture which relays on a hybrid virtualization framework. We describe its functional components and dataflow and highlight the next steps that we will adopt in order to realize it and evaluate its feasibility and effectiveness.

In this paper we propose a many-core implementation of evolutionary computation for GPGPU (General-Purpose Graphic Processing Unit) to solve non-convex Mixed Integer Non-Linear Programming (MINLP) and non-convex Non Linear Programming (NLP) problems using a stochastic algorithm. Stochastic algorithms being random in their behavior are difficult to implement over GPU like architectures. In this paper we not only succeed in implementation of a stochastic algorithm over GPU but show considerable speedups over CPU implementations. The stochastic algorithm considered for this paper is an adaptive resolution approach to genetic algorithm (arGA), developed by the authors of this paper. The technique uses the entropy measure of each variable to adjust the intensity of the genetic search around promising individuals. Performance is further improved by hybridization with adaptive resolution local search (arLS) operator. In this paper, we describe the challenges and design choices involved in parallelization of this algorithm to solve complex MINLPs over a commodity GPU using Compute Unified Device Architecture (CUDA) programming model. Results section shows several numerical tests and performance measurements obtained by running the algorithm over an nVidia Fermi GPU. We show that for difficult problems we can obtain a speedup of up to 20x with double precision and up to 42x with single precision.

Future trend of supercomputing goes toward exa flops, which is realized by millions of cores expected to be installed on around 2018. Such massive parallelism makes programming difficult. Inherent parallel nature of evolutionary computation is a promising factor in designing optimization algorithms that adapt to such massively parallel architecture although there are some problems to be solved to realize robust algorithm that can analyze complex interactions among genes. This paper discusses current status and future trend in realizing robust and scalable evolutionary computation on such extreme scale supercomputers.

Led by General Purpose computing over Graphical Processing Units (GPGPUs), the parallel computing area is witnessing a rapid change in dominant parallel systems. A major hurdle in this switch is the Single Instruction Multiple Thread (SIMT) architecture of GPUs which is usually not suitable for the design of legacy parallel algorithms. Genetic Algorithms (GAs) is no exception for that. GAs are commonly parallelized due to the high demanding computational needs. Given the performance of GPGPUs, the need to best exploit them to maximize computing efficiency for parallel GAs is demandingly growing. The goal of this paper is to shed light on the challenges parallel GAs designers/programmers will likely face while trying to achieve this, and to provide some practical advice on how to maximize GPGPU exploitation as a result. To that end, this paper provides a study on adapting legacy parallel GAs on GPGPU systems. The paper exposes the design challenges of nVidia's GPU architecture to the parallel GAs community by: discussing features of GPU, reviewing design issues in GPU relevant to parallel GAs, the design and introduction of new techniques to achieve an efficient implementation for parallel GAs and observing the effect of the pivotal points that both capitalize on the strengths of GPU and limit the deficiencies/overheads of GPUs. The paper demonstrates the performance of designed-for-GPGPU parallel GAs representing the entire spectrum of legacy parallel model of GAs over nVidia Tesla C1060 workstation showing a significant improvement in performance after optimizing and tuning the algorithms for GPU.

Cloud computing is impacting the modern Internet computing and businesses in every aspect. One feature of clouds is the convenience of using the services offered by the cloud. Consequently, most cloud service providers use WS for users and developers to interface with the cloud. However, the current cloud WS are focused into core and fundamental modern computing functionalities. We anticipate as cloud developments tools mature and cloud applications become more popular, there will be an opportunity for designing and implementing applications/services to be embedded in the cloud for use by applications in the cloud. We propose a framework for WS deployment in the cloud to be usable by applications residing in the same cloud. The framework capitalizes on the cloud strong points to offer a higher value to the service consumer inside the cloud. The authoritative nature of clouds would enable more efficient models for WS publishing, indexing and description. Moreover, being hosted in the cloud, WScan build on the high scalability offered by the cloud with a much higher reliability. Finally, scheduling the instances using the WS in bundle with the WS instances could offer a LAN-like connectivity performance driving down the latency to the magnitude of lower microseconds. In this paper, we highlight the challenges and opportunities of cloud applications using cloud embedded Web services. We give a description of the different aspects by illustrating the different components, together with an end-to-end use case to show the applicability of the proposed system.

This paper proposes a novel crossover operator for solving large-scale traveling salesman problems (TSPs) by using a Hybrid Genetic Algorithm (HGA) with Lin-Kernighan heuristic for local search and we tentatively name Zoning Crossover (Z-Cross). The outline of Z-Cross is firstly to set a zone in the travelling area according to some rules, secondly to cut edges connecting cities between inside and outside the zone, thirdly to exchange edges inside the zone of one parent and those of the other parent, and lastly to reconnect sub-tours and isolated cities, which come about in the 3rd step mentioned above, so as to construct a new tour of TSP. The method is compared with conventional three crossovers; those are the Maximal Preservative Crossover, the Greedy Sub-tour Crossover and the Edge Recombination Crossover, and evaluated from the viewpoints of tour quality and CPU time. Ten benchmarks are selected from the well-known TSP website of Georgia Institute of Technology, whose names are xqf131, xqg237, ..., sra104815. The experiments are performed ten times for each crossover and each benchmark and show that the Z-Cross succeeds in finding better solution and running faster than the conventional methods. Six benchmarks with size from 39,603 to 104,815 cities are selected from the TSP website and challenged the records of tour lengths. The Z-Cross betters the record of the problem rbz43748 and approaches to solutions less than only 0.02% over the known best solutions for five instances.

A principal fragment-based design approach is De Novo ligand design at which small-molecule structures from a database of existing compounds (or compounds that could be made) are docked into the protein binding site following a virtual synthesis scheme. New virtual structures can easily be constructed from combinatorial building blocks. Typically, tens of thousands of orientations are generated for each ligand candidate, therefore global optimization algorithms are usually employed to search the chemical space by generating new molecular structures through probing many different fragments in a combinatorial fashion. We propose using Bayesian Optimization Algorithm (BOA), a meta-heuristic algorithm, in searching the combination of pre-docked fragments through minimizing the energy of ligand-receptor docking. We further introduce the use of GPU (Graphical Processing Unit) to overcome the very long time required in evaluating each possible fragment combination. We show how the GPU utilization enables experimenting larger fragments and target receptors for more complex instances. The experiments resulted in regenerating three drug-like compounds defined in the ZINC database as well as finding a new compound. The Results show how the nVidia's Tesla C1060 GPU was utilized to accelerate the docking process by two orders of magnitude.

General purpose computing over graphical processing units (GPGPUs) is a huge shift of paradigm in parallel computing that promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design and software development. In this paper we describe the challenges and design choices involved in parallelization of Bayesian optimization algorithm (BOA) to solve complex combinatorial optimization problems over nVidia commodity graphics hardware using compute unified device architecture (CUDA). BOA is a well-known multivariate estimation of distribution algorithm (EDA) that incorporates methods for learning Bayesian network (BN). It then uses BN to sample new promising solutions. Our implementation is fully compatible with modern commodity GPUs and therefore we call it gBOA (BOA on GPU). In the results section, we show several numerical tests and performance measurements obtained by running gBOA over an nVidia Tesla C1060 GPU. We show that in the best case we can obtain a speedup of up to 13x.

This paper empirically investigates parallel competent genetic algorithms (cGAs) [4]. cGAs, such as BOA [21], LINCGA [15], D5-GA [28], can solve GA-difficult problems by automatically learning problem structure as gene linkage. Parallel implementation of cGAs can reduce computational cost due to the linkage learning and give us problem solving environments for a wide spectrum of real-world problems. Although some parallel cGAs have been proposed [16, 18, 19], the effect of the parallelizations has not been investigated enough. This paper empirically discusses the applicability and property of parallel cGAs, including a new parallel cGA, parallel D5-GA.

This paper presents a method to solve large instances of capacitated vehicle routing problem (CVRP) using cellular genetic algorithm (cGA) with local search (LS) over cell broadband engine (cell BE) architecture. We propose a unique parallelization model where computationally intensive local search (LS) runs on the available synergistic processing elements (SPEs) in parallel, while the power processor element (PPE) runs the cGA and acts as a controller for all the SPEs. We reproduce the results from earlier work in PPE only implementation of the algorithm, and we show a considerable reduction in execution time for parallel implementation over cell BE. Moreover, we extended it further to solve larger instances of CVRP (compared to the ones present in the CVRP literature), and got acceptable results in a reasonable amount of time.

This paper gives a survey about the impact of modern parallel/distributed computing paradigms over parallel genetic algorithms (PGAs). Helping the GA community to feel more comfortable with the evolving parallel paradigms, and marking some areas of research for the high-performance computing (HPC) community is the major inspiration behind this survey. In the modern parallel computing paradigms we have considered only two major areas that have evolved very quickly during the past few years, namely, multicore computing and Grid computing. We discuss the challenges involved, and give potential solutions for these challenges. We also propose a hierarchical PGA suitable for Grid environment with multicore computational resources.

This paper is a step towards a general purpose optimization problem-solving framework that can solve a large number of global optimization problems on its own with a min imal input from the user. It relies on competent GAs (Genetic Algorithms) as the solver and depends on Grid computing for the required computational resources. In this paper we will discuss the architecture of the framework in detail. In the results section we will discuss the speedups obtained by using parallel GAs over a Grid computing environment and the effects of Grid overheads on the speedup. Even though there are various advantages of using Grids but in the results section we will focus on the reduction in total execution time due to parallelism.

Efficient mixing of building blocks is important for genetic algorithms and linkage identification that identify variables tightly linked to form a building block have been proposed. In this paper, we apply D5-GA with CDC - a genetic algorithm incorporating a linkage identification method called D5and a crossover method called CDC - to a network design problem to verify its performance and examine the applicability of the linkage identification genetic algorithms.

This paper introduces MHGrid, a framework that exploits meta-heuristics based search methods and grid computing to enable the transparent sharing of heterogeneous and dynamic resources offering a grid based global optimization framework. MHGrid allows a user to solve almost all kinds of global optimization problems in a black box manner with a minimal input from the user, it also allows the user to integrate his own solver into MHGrid. In this paper we will discuss the architecture and motivation of such a system. We will also discuss the challenges/complexities involved in constructing MHGrid.

In this paper we discuss the optimization problems with noisy fitness function. On financial optimization problems, Monte-Carlo method is commonly used to evaluate the optimization criteria such as value at risk. The evaluation model is often very complex which needs considerable computational overheads. In order to realize efficient optimization of financial problems, we propose a method to decide the number of samples used to estimate the optimization criteria. Selection efficiency proposed in this paper is a index that shows how close the population approaches to the convergence to a good solution. In general, it is difficult to calculate selection efficiency analytically. Thus we also employ bootstrap method to estimate selection efficiency. The resulting algorithm is applied to the optimization of the procurement plan optimization problem. The result shows that value at risk of the problem is optimized efficiently by the proposed method.

We propose a crossover method to combine complexly overlapping building blocks (BBs). Although there have been several techniques to identify linkage sets of loci o form a BB [4, 6, 7, 10, 11], the way to to realize effective crossover from the linkage information from such techniques has not been studied enough. Especially for problems with overlapping BBs, a crossover method proposed by Yu et al. [13] is the first and only known research, however it cannot perform well for problems with complexly overlapping BBs due to insufficient variety of crossover sites. In this paper, we propose a crossover method which examines values of given parental strings minutely and defines which variables are exchanged to produce new and different strings without increasing BB disruptions as much as possible. The method is combined with a scalable linkage identification technique to construct an efficient algorithm for problems with overlapping BBs. We design test functions with controllable complexity of overlap and test the method with the functions.

Probabilistic model-building genetic algorithms such as extended compact genetic algorithm (ECGA) are proposed to solve difficult problems for classical genetic algorithms. Probabilistic model-building process based on marginal product model needs extensive computational overheads in ECGA. This paper discusses ECGA with linkage re-utilization and local search to reduce its model-building cost. Through simulation studies, we show the effectiveness of our approach that can reduce overall computational overheads.

Estimation of distribution algorithms (EDAs) are population based evolutionary algorithms derived from genetic algorithms (GAs) . EDAs build probabilistic models of promising solutions to guide further exploration of the search space. They have been considered to behave in similar way to GAs. In this paper, we show their different behaviors and difficulties in applications of EDAs by designing an EDA difficult function in which schemata that are not consistent with problem structure sometimes overwhelm those that are.

Genetic Algorithms perform crossovers effectively when linkage sets - sets of variables tightly linked to form building blocks - are identified. Several methods have been proposed to detect the linkage sets. Perturbation methods (PMs) investigate fitness differences by perturbations of gene values and Estimation of distribution algorithms (EDAs) estimate the distribution of promising strings. In this paper, we propose a novel approach combining both of them, which detects dependencies of variables by estimating the distribution of strings clustered according to fitness differences. The proposed algorithm, called the Dependency Detection for Distribution Derived from fitness Differences (D(5)), can detect dependencies of a class of functions that are difficult for EDAs, and requires less computational cost than PMs.

This paper discusses a parallel optimization algorithm based on evolutionary algorithms with probabilistic model-building in order to design a robust search algorithm that can be applicable to a wide-spectrum of application problems effectively and reliably. Probabilistic model building genetic algorithm, which is also called estimation of distribution algorithm, is a promising approach in evolutionary computation and its parallelization has been investigated. We propose an improvement of parallel network construction in distributed Bayesian optimization algorithms which estimate distribution of promising solutions as Bayesian networks. Through numerical experiments on an actual parallel architecture, we show the effectiveness of our approach compared to the conventional parallelization. Also we perform experiments on a real-world application problem: protein structure predictions.

In order to enhance efficiency of genetic algorithms, it is important to identify a linkage set, i.e. a set of loci tightly linked to construct a building block. In this paper, we propose a novel linkage identification method for real-valued strings called the real-valued dependency detection for distribution derived from df (rD/sup 5/). It can detect linkage sets with quasilinear fitness evaluations. The rD/sup 5/ is designed based on the D/sup 5/ which has been proposed for binary strings. It detects dependencies of loci by estimating the distribution of strings classified according to fitness differences. The rD/sup 5/ and the LINC-R which is one of linkage identification methods proposed elsewhere, provide approximate equivalent information about a function to be solved, however, the rD/sup 5/ performs smaller number of fitness evaluations than the LINC-R for larger functions. Although estimation of distribution algorithms (EDAs) also estimate distribution of strings, it is difficult for EDAs to solve a function composed of exponentially scaled subfunctions. The proposed method, by contrast, can be applied to the function in the similar way to as to a function composed of uniformly scaled subfunctions which is easy for EDAs. We perform experiments to compare the proposed method with the LINC-R and to examine the scaling effect stability of the rD/sup 5/. We also investigate two parameters, that define the amount of perturbation (mutation) and that define the quantization level.

Genetic algorithms (GAs) process building blocks (BBs) mixed and tested through genetic recombination operators. To realize effective BB processing, linkage identification, which detects a set of tightly linked loci, is essential. This paper proposes linkage identification with epistasis measures (LIEM), which detects linkage groups based on a pair-wise epistasis measure.

The paper discusses the improvement of genetic operators and fitness evaluation policies of the genetic adaptive routing algorithm we have proposed elsewhere. First, we introduce a threshold policy in evaluating link load status that is commonly employed in dynamic load balancing algorithms. Second, we discuss policies to trigger link load status observations to evaluate fitness values. Third, we introduce adaptive path mutation and path crossover operators to enhance their ability to generate well-performed alternative routes. Through empirical studies, we investigate an optimal way for load status observations and validate the effectiveness of the adaptive genetic operators.

This paper presents the linkage identification by non-monotonicity detection (LIMD) procedure and its extension for overlapping functions by introducing the tightness detection (TD) procedure. The LIMD identifies linkage groups directly by performing order-2 simultaneous perturbations on a pair of loci to detect monotonicity/non-monotonicity of fitness changes. The LIMD can identify linkage groups with at most order of k when it is applied to O(2(k)) strings. The TD procedure calculates tightness of linkage between a pair of loci based on the linkage groups obtained by the LIMD. By removing loci with weak tightness from linkage groups, correct linkage groups are obtained for overlapping functions, which were considered difficult for linkage identification procedures.

This paper presents a string migration scheme for an adaptive network routing algorithm called a genetic routing algorithm which employs genetic operators to create alternative routes in a routing table. String migrations are employed usually in islands model of parallel or distributed genetic algorithms, which exchange strings among subpopulations to accelerate their convergence. We propose a tailored version of string migration for the genetic routing algorithm in order to realize effective information exchanges among nodes to have optimal route with less communication overhead in the network.