Search Results (14)

Population-based metaheuristics can be seen as a set of agents that smartly explore the space of solutions of a given optimization problem. These agents are commonly governed by movement operators that decide how the exploration is driven. Although metaheuristics have successfully been used for more than 20 years, performing rapid and high-quality parameter control is still a main concern. For instance, deciding the proper population size yielding a good balance between quality of results and computing time is constantly a hard task, even more so in the presence of an unexplored optimization problem. In this paper, we propose a self-adaptive strategy based on the on-line population balance, which aims for improvements in the performance and search process on population-based algorithms. The design behind the proposed approach relies on three different components. Firstly, an optimization-based component which defines all metaheuristic tasks related to carry out the resolution of the optimization problems. Secondly, a learning-based component focused on transforming dynamic data into knowledge in order to influence the search in the solution space. Thirdly, a probabilistic-based selector component is designed to dynamically adjust the population. We illustrate an extensive experimental process on large instance sets from three well-known discrete optimization problems: Manufacturing Cell Design Problem, Set covering Problem, and Multidimensional Knapsack Problem. The proposed approach is able to compete against classic, autonomous, as well as IRace-tuned metaheuristics, yielding interesting results and potential future work regarding dynamically adjusting the number of solutions interacting on different times within the search process. Full article

eHealth services require continuous data streaming and a stable level of quality of service. However, wireless network connections can be characterized by variable bandwidths. This requires continuous adaptation of systems, including adapting the bit rates of data streamed by sensors. Assigning appropriate rates to the data represents a main task in congestion control. Most of the current methods look for proper sensor data rates within continuous domains. We examine the case when sensors can generate data streams with several different qualities (e.g., sampling rates, sampling accuracies, etc.). For this reason, the domain of the data rate values can be restricted to the discrete values representing the data rates of the possible quality variations. This paper examines the optimization of the utility of the delivered data under resource constraints by selecting an appropriate variation of the provided data from a discrete set. We provide a formal model for delivering data streams in WBANs and recommend an optimization algorithm to solve the problem. Our recommended solutions are related to the multiple-choice multidimensional knapsack problem. By comparing the proposed algorithms, we found that the greedy method closely approximates the optimum in a short running time. Full article

This paper presents a set of adaptive parameter control methods through reinforcement learning for the particle swarm algorithm. The aim is to adjust the algorithm’s parameters during the run, to provide the metaheuristics with the ability to learn and adapt dynamically to the problem and its context. The proposal integrates Q–Learning into the optimization algorithm for parameter control. The applied strategies include a shared Q–table, separate tables per parameter, and flexible state representation. The study was evaluated through various instances of the multidimensional knapsack problem belonging to the $\mathcal{NP}$-hard class. It can be formulated as a mathematical combinatorial problem involving a set of items with multiple attributes or dimensions, aiming to maximize the total value or utility while respecting constraints on the total capacity or available resources. Experimental and statistical tests were carried out to compare the results obtained by each of these hybridizations, concluding that they can significantly improve the quality of the solutions found compared to the native version of the algorithm. Full article

The assignment of tasks for unmanned aerial vehicles (UAVs) during forest fire reconnaissance is a highly complex and large-scale problem. Current task allocation methods struggle to strike a balance between solution speed and effectiveness. In this paper, a two-phase centralized UAV task assignment model based on expectation maximization (EM) clustering and the multidimensional knapsack model (MKP) is proposed for the forest fire reconnaissance task assignment. The fire situation information is acquired using the sensors carried by satellites at first. Then, the EM algorithm based on the Gaussian mixture model (GMM) is applied to get the initial position of every UAV. In the end, the MKP is applied for UAV task assignment based on the initial positions of the UAVs. An improved genetic algorithm (GA) based on the fireworks algorithm (FWA) is proposed for faster iteration speed. A simulation was carried out against the background of forest fires in Liangshan Prefecture, Sichuan Province, and the simulation’s results demonstrate that the task assignment model can quickly and effectively address task allocation problems on a large scale. In addition, the FW–GA hybrid algorithm has great advantages over the traditional GA, particularly in solving time, iteration convergence speed, and solution effectiveness. It can reduce up to 556% of the iteration time and increase objective function value by 1.7% compared to the standard GA. Furthermore, compared to the GA–SA algorithm, its solving time is up to 60 times lower. This paper provides a new idea for future large-scale UAV task assignment problems. Full article

The moth search algorithm (MS) is a relatively new metaheuristic optimization algorithm which mimics the phototaxis and Lévy flights of moths. Being an NP-hard problem, the 0–1 multidimensional knapsack problem (MKP) is a classical multi-constraint complicated combinatorial optimization problem with numerous applications. In this paper, we present a hybrid learning MS (HLMS) by incorporating two learning mechanisms, global-best harmony search (GHS) learning and Baldwinian learning for solving MKP. (1) GHS learning guides moth individuals to search for more valuable space and the potential dimensional learning uses the difference between two random dimensions to generate a large jump. (2) Baldwinian learning guides moth individuals to change the search space by making full use of the beneficial information of other individuals. Hence, GHS learning mainly provides global exploration and Baldwinian learning works for local exploitation. We demonstrate the competitiveness and effectiveness of the proposed HLMS by conducting extensive experiments on 87 benchmark instances. The experimental results show that the proposed HLMS has better or at least competitive performance against the original MS and some other state-of-the-art metaheuristic algorithms. In addition, the parameter sensitivity of Baldwinian learning is analyzed and two important components of HLMS are investigated to understand their impacts on the performance of the proposed algorithm. Full article

With the rapid development of virtual reality (VR) technology, this paper proposes an access point (AP) correlation method based on VR user behavior awareness to address the problem of how current AP correlation methods only focus on the performance improvements of ordinary users and ignore the impact of VR user behavior on service quality. This paper analyzes the AP association method under the coverage scenario of a multi-access point (multi-AP) scenario environment and controls the performance improvement of VR user APs or APs under the access controller (AC) by association. Firstly, the VR network application scenario and system model were constructed, and secondly, the user behavior was sensed by analyzing the viewing habits of users. Then, the VR user association problem based on VR user behavior perception was transformed into a “many-to-many” matching problem between VR user devices and APs, and the generalized multidimensional multiple choice knapsack (GMMKP) model was established to solve the problem using the backpack problem theory; the suboptimal solution algorithm was selected to obtain the best VR user AP association strategy. The experimental results show by simulation that the proposed algorithm in this paper performed better in terms of the AP load balancing and average network download latency compared to the comparison algorithms. Full article

Nature–inspired computing is a promising field of artificial intelligence. This area is mainly devoted to designing computational models based on natural phenomena to address complex problems. Nature provides a rich source of inspiration for designing smart procedures capable of becoming powerful algorithms. Many of these procedures have been successfully developed to treat optimization problems, with impressive results. Nonetheless, for these algorithms to reach their maximum performance, a proper balance between the intensification and the diversification phases is required. The intensification generates a local solution around the best solution by exploiting a promising region. Diversification is responsible for finding new solutions when the main procedure is trapped in a local region. This procedure is usually carryout by non-deterministic fundamentals that do not necessarily provide the expected results. Here, we encounter the stagnation problem, which describes a scenario where the search for the optimum solution stalls before discovering a globally optimal solution. In this work, we propose an efficient technique for detecting and leaving local optimum regions based on Shannon entropy. This component can measure the uncertainty level of the observations taken from random variables. We employ this principle on three well–known population–based bio–inspired optimization algorithms: particle swarm optimization, bat optimization, and black hole algorithm. The proposal’s performance is evidenced by solving twenty of the most challenging instances of the multidimensional knapsack problem. Computational results show that the proposed exploration approach is a legitimate alternative to manage the diversification of solutions since the improved techniques can generate a better distribution of the optimal values found. The best results are with the bat method, where in all instances, the enhanced solver with the Shannon exploration strategy works better than its native version. For the other two bio-inspired algorithms, the proposal operates significantly better in over 70% of instances. Full article

In order to minimize execution times, improve the quality of solutions, and address more extensive target situations, optimization techniques, particularly metaheuristics, are continually improved. Hybridizing procedures are one of these noteworthy strategies due to their wide range of applications. This article describes a hybrid algorithm that combines the k-means method to produce a binary version of the cuckoo search and sine cosine algorithms. The binary algorithms are applied on the $\mathcal{NP}$-hard multi-demand multidimensional knapsack problem. This problem is of particular interest because it has two types of constraints. The first group of constraints is related to the capacity of the knapsacks, and a second type is associated with the demand that must be met. Experiments were undertaken to acquire insight into the contribution of the k-means technique and the local search operator to the final results. Additionally, a comparison is made with two other types of binarization, the first based on a random method and the second based on the percentile concept. The results reveal that the k-means hybrid algorithm consistently provides superior results in most cases studied. In particular, incorporating the local search operator improved the results by an average of 0.23%. On the other hand, when comparing the results with 100 items and 30-30 restrictions, k-means was 1.06% better on average than the random operator. Full article

Population-based approaches have given us new search strategies and ideas in order to solve optimization problems. Usually, these methods are based on the performance carried out by a finite number of agents, which by the interaction between them they evolve and work all over the search space. Also, it is well-known that the correct employment of parameter values in this kind of method can positively impact their performance and behavior. In this context, the present work focuses on the design of a hybrid architecture which smartly balances the population size on run-time. In order to smartly balance and control the population size, a modular approach, named Linear Modular Population Balancer (LMPB), is proposed. The main ideas behind the designed architecture include the solving strategy behind a population-based metaheuristic, the influence of learning components based on multiple statistical modeling methods which transform the dynamic data generated into knowledge, and the possibilities to tackle both discrete and continuous optimization problems. In this regard, three modules are proposed for LMPB, which concern tasks such as the management of the population-based algorithm, parameter setting, probabilities, learning methods, and selection mechanism for the population size to employ. In order to test the viability and effectiveness of our proposed approach, we solve a set of well-known benchmark functions and the multidimensional knapsack problem (MKP). Additionally, we illustrate promising solving results, compare them against state-of-the-art methods which have proved to be good options for solving optimization problems, and give solid arguments for future work in the necessity to keep evolving this type of proposed architecture. Full article

We propose a memetic algorithm for the multiple-choice multidimensional knapsack problem (MMKP). In this study, we focus on finding good solutions for the MMKP instances, for which feasible solutions rarely exist. To find good feasible solutions, we introduce a novel repair heuristic based on the tendency function and a genetic search for the function approximation. Even when the density of feasible solutions over the entire solution space is very low, the proposed repair heuristic could successfully change infeasible solutions into feasible ones. Based on the proposed repair heuristic and effective local search, we designed a memetic algorithm that performs well on problem instances with a low density of feasible solutions. By performing experiments, we could show the superiority of our method compared with previous genetic algorithms. Full article

This paper presents a methodological scheme to obtain the maximum benefit in occupational health by attending to psychosocial risk factors in a company. This scheme is based on selecting an optimal subset of psychosocial risk factors, considering the departments’ budget in a company as problem constraints. This methodology can be summarized in three steps: First, psychosocial risk factors in the company are identified and weighted, applying several instruments recommended by business regulations. Next, a mathematical model is built using the identified psychosocial risk factors information and the company budget for risk factors attention. This model represents the psychosocial risk optimization problem as a Multidimensional Knapsack Problem (MKP). Finally, since Multidimensional Knapsack Problem is NP-hard, one simulated annealing algorithm is applied to find a near-optimal subset of factors maximizing the psychosocial risk care level. This subset is according to the budgets assigned for each of the company’s departments. The proposed methodology is detailed using a case of study, and thirty instances of the Multidimensional Knapsack Problem are tested, and the results are interpreted under psychosocial risk problems to evaluate the simulated annealing algorithm’s performance (efficiency and efficacy) in solving these optimization problems. This evaluation shows that the proposed methodology can be used for the attention of psychosocial risk factors in real companies’ cases. Full article

Ant colony optimization is a metaheuristic that is mainly used for solving hard combinatorial optimization problems. The distinctive feature of ant colony optimization is a learning mechanism that is based on learning from positive examples. This is also the case in other learning-based metaheuristics such as evolutionary algorithms and particle swarm optimization. Examples from nature, however, indicate that negative learning—in addition to positive learning—can beneficially be used for certain purposes. Several research papers have explored this topic over the last decades in the context of ant colony optimization, mostly with limited success. In this work we present and study an alternative mechanism making use of mathematical programming for the incorporation of negative learning in ant colony optimization. Moreover, we compare our proposal to some well-known existing negative learning approaches from the related literature. Our study considers two classical combinatorial optimization problems: the minimum dominating set problem and the multi dimensional knapsack problem. In both cases we are able to show that our approach significantly improves over standard ant colony optimization and over the competing negative learning mechanisms from the literature. Full article

This article proposes a hybrid algorithm that makes use of the db-scan unsupervised learning technique to obtain binary versions of continuous swarm intelligence algorithms. These binary versions are then applied to large instances of the well-known multidimensional knapsack problem. The contribution of the db-scan operator to the binarization process is systematically studied. For this, two random operators are built that serve as a baseline for comparison. Once the contribution is established, the db-scan operator is compared with two other binarization methods that have satisfactorily solved the multidimensional knapsack problem. The first method uses the unsupervised learning technique k-means as a binarization method. The second makes use of transfer functions as a mechanism to generate binary versions. The results show that the hybrid algorithm using db-scan produces more consistent results compared to transfer function (TF) and random operators. Full article

In this paper, The Multidimensional Knapsack Problem (MKP) which occurs in many different applications is studied and a genetic algorithm to solve the MKP is proposed. Unlike the technique of the classical genetic algorithm, initial population is not randomly generated in the proposed algorithm, thus the solution space is scanned more efficiently. Moreover, the algorithm is written in C programming language and is tested on randomly generated instances. It is seen that the algorithm yields optimal solutions for all instances. Full article