Search results for: knapsack problem
7107 An Approximation Algorithm for the Non Orthogonal Cutting Problem
Abstract:
We study the problem of cutting a rectangular material entity into smaller sub-entities of trapezoidal forms with minimum waste of the material. This problem will be denoted TCP (Trapezoidal Cutting Problem). The TCP has many applications in manufacturing processes of various industries: pipe line design (petro chemistry), the design of airfoil (aeronautical) or cuts of the components of textile products. We introduce an orthogonal build to provide the optimal horizontal and vertical homogeneous strips. In this paper we develop a general heuristic search based upon orthogonal build. By solving two one-dimensional knapsack problems, we combine the horizontal and vertical homogeneous strips to give a non orthogonal cutting pattern.Keywords: combinatorial optimization, cutting problem, heuristic
Procedia PDF Downloads 5357106 Novel Animal Drawn Wheel-Axle Mechanism Actuated Knapsack Boom Sprayer
Authors: Ibrahim O. Abdulmalik, Michael C. Amonye, Mahdi Makoyo
Abstract:
Manual knapsack sprayer is the most popular means of farm spraying in Nigeria. It has its limitations. Apart from the human fatigue, which leads to unsteady walking steps, their field capacities are small. They barely cover about 0.2hectare per hour. Their small swath implies that a sizeable farm would take several days to cover. Weather changes are erratic and often it is desired to spray a large farm within hours or few days for even effect, uniformity and to avoid adverse weather interference. It is also often required that a large farm be covered within a short period to avoid re-emergence of weeds before crop emergence. Deployment of many knapsack operators to large farms has not been successful. Human error in taking equally spaced swaths usually result in over dosage of overlaps and in unapplied areas due to error at edges overlaps. Large farm spraying require boom equipment with larger swath. Reduced error in swath overlaps and spraying within the shortest possible time are then assured. Tractor boom sprayers would readily overcome these problems and achieve greater coverage, but they are not available in the country. Tractor hire for cultivation is very costly with the attendant lack of spare parts and specialized technicians for maintenance wherefore farmers find it difficult to engage tractors for cultivation and would avoid considering the employment of a tractor boom sprayer. Animal traction in farming is predominant in Nigeria, especially in the Northern part of the country. Development of boom sprayers drawn by work animals surely implies the maximization of animal utilization in farming. The Hydraulic Equipment Development Institute, Kano, in keeping to its mandate of targeted R&D in hydraulic and pneumatic systems, has developed an Animal Drawn Knapsack Boom Sprayer with four nozzles using the axle mechanism of a two wheeled cart to actuate the piston pump of two knapsack sprayers in line with appropriate technology demand of the country. It is hoped that the introduction of this novel contrivance shall enhance crop protection practice and lead to greater crop and food production in Nigeria.Keywords: boom, knapsack, farm, sprayer, wheel axle
Procedia PDF Downloads 2807105 Chairussyuhur Arman, Totti Tjiptosumirat, Muhammad Gunawan, Mastur, Joko Priyono, Baiq Tri Ratna Erawati
Authors: Maria M. Giannakou, Athanasios K. Ziliaskopoulos
Abstract:
Transmission pipelines carrying natural gas are often routed through populated cities, industrial and environmentally sensitive areas. While the need for these networks is unquestionable, there are serious concerns about the risk these lifeline networks pose to the people, to their habitat and to the critical infrastructures, especially in view of natural disasters such as earthquakes. This work presents an Integrated Pipeline Risk Management methodology (IPRM) for assessing the hazard associated with a natural gas pipeline failure due to natural or manmade disasters. IPRM aims to optimize the allocation of the available resources to countermeasures in order to minimize the impacts of pipeline failure to humans, the environment, the infrastructure and the economic activity. A proposed knapsack mathematical programming formulation is introduced that optimally selects the proper mitigation policies based on the estimated cost – benefit ratios. The proposed model is demonstrated with a small numerical example. The vulnerability analysis of these pipelines and the quantification of consequences from such failures can be useful for natural gas industries on deciding which mitigation measures to implement on the existing pipeline networks with the minimum cost in an acceptable level of hazard.Keywords: cost benefit analysis, knapsack problem, natural gas distribution network, risk management, risk mitigation
Procedia PDF Downloads 2867104 Exploring Counting Methods for the Vertices of Certain Polyhedra with Uncertainties
Authors: Sammani Danwawu Abdullahi
Abstract:
Vertex Enumeration Algorithms explore the methods and procedures of generating the vertices of general polyhedra formed by system of equations or inequalities. These problems of enumerating the extreme points (vertices) of general polyhedra are shown to be NP-Hard. This lead to exploring how to count the vertices of general polyhedra without listing them. This is also shown to be #P-Complete. Some fully polynomial randomized approximation schemes (fpras) of counting the vertices of some special classes of polyhedra associated with Down-Sets, Independent Sets, 2-Knapsack problems and 2 x n transportation problems are presented together with some discovered open problems.Keywords: counting with uncertainties, mathematical programming, optimization, vertex enumeration
Procedia PDF Downloads 3477103 Solving the Transportation Problem for Warehouses and Dealers in Bangalore City
Authors: S. Aditya, K. T. Nideesh, N. Guruprasad
Abstract:
Being a subclass of linear programing problem, the Transportation Problem is a classic Operations Research problem where the objective is to determine the schedule for transporting goods from source to destination in a way that minimizes the shipping cost while satisfying supply and demand constraints. In this paper, we are representing the transportation problem for various warehouses along with various dealers situated in Bangalore city to reduce the transportation cost incurred by them as of now. The problem is solved by obtaining the Initial Basic feasible Solution through various methods and further proceeding to obtain optimal cost.Keywords: NW method, optimum utilization, transportation problem, Vogel’s approximation method
Procedia PDF Downloads 4327102 Using Convergent and Divergent Thinking in Creative Problem Solving in Mathematics
Authors: Keng Keh Lim, Zaleha Ismail, Yudariah Mohammad Yusof
Abstract:
This paper aims to find out how students using convergent and divergent thinking in creative problem solving to solve mathematical problems creatively. Eight engineering undergraduates in a local university took part in this study. They were divided into two groups. They solved the mathematical problems with the use of creative problem solving skills. Their solutions were collected and analyzed to reveal all the processes of problem solving, namely: problem definition, ideas generation, ideas evaluation, ideas judgment, and solution implementation. The result showed that the students were able to solve the mathematical problem with the use of creative problem solving skills.Keywords: convergent thinking, divergent thinking, creative problem solving, creativity
Procedia PDF Downloads 3427101 Fuzzy Vehicle Routing Problem for Extreme Environment
Authors: G. Sirbiladze, B. Ghvaberidze, B. Matsaberidze
Abstract:
A fuzzy vehicle routing problem is considered in the possibilistic environment. A new criterion, maximization of expectation of reliability for movement on closed routes is constructed. The objective of the research is to implement a two-stage scheme for solution of this problem. Based on the algorithm of preferences on the first stage, the sample of so-called “promising” routes will be selected. On the second stage, for the selected promising routes new bi-criteria problem will be solved - minimization of total traveled distance and maximization of reliability of routes. The problem will be stated as a fuzzy-partitioning problem. Two possible solutions of this scheme are considered.Keywords: vehicle routing problem, fuzzy partitioning problem, multiple-criteria optimization, possibility theory
Procedia PDF Downloads 5427100 Partial Knowledge Transfer Between the Source Problem and the Target Problem in Genetic Algorithms
Authors: Terence Soule, Tami Al Ghamdi
Abstract:
To study how the partial knowledge transfer may affect the Genetic Algorithm (GA) performance, we model the Transfer Learning (TL) process using GA as the model solver. The objective of the TL is to transfer the knowledge from one problem to another related problem. This process imitates how humans think in their daily life. In this paper, we proposed to study a case where the knowledge transferred from the S problem has less information than what the T problem needs. We sampled the transferred population using different strategies of TL. The results showed transfer part of the knowledge is helpful and speeds the GA process of finding a solution to the problem.Keywords: transfer learning, partial transfer, evolutionary computation, genetic algorithm
Procedia PDF Downloads 1237099 Bee Colony Optimization Applied to the Bin Packing Problem
Authors: Kenza Aida Amara, Bachir Djebbar
Abstract:
We treat the two-dimensional bin packing problem which involves packing a given set of rectangles into a minimum number of larger identical rectangles called bins. This combinatorial problem is NP-hard. We propose a pretreatment for the oriented version of the problem that allows the valorization of the lost areas in the bins and the reduction of the size problem. A heuristic method based on the strategy first-fit adapted to this problem is presented. We present an approach of resolution by bee colony optimization. Computational results express a comparison of the number of bins used with and without pretreatment.Keywords: bee colony optimization, bin packing, heuristic algorithm, pretreatment
Procedia PDF Downloads 6287098 A Method for Solving a Bi-Objective Transportation Problem under Fuzzy Environment
Authors: Sukhveer Singh, Sandeep Singh
Abstract:
A bi-objective fuzzy transportation problem with the objectives to minimize the total fuzzy cost and fuzzy time of transportation without according priorities to them is considered. To the best of our knowledge, there is no method in the literature to find efficient solutions of the bi-objective transportation problem under uncertainty. In this paper, a bi-objective transportation problem in an uncertain environment has been formulated. An algorithm has been proposed to find efficient solutions of the bi-objective transportation problem under uncertainty. The proposed algorithm avoids the degeneracy and gives the optimal solution faster than other existing algorithms for the given uncertain transportation problem.Keywords: uncertain transportation problem, efficient solution, ranking function, fuzzy transportation problem
Procedia PDF Downloads 5197097 Cooperative Coevolution for Neuro-Evolution of Feed Forward Networks for Time Series Prediction Using Hidden Neuron Connections
Authors: Ravneil Nand
Abstract:
Cooperative coevolution uses problem decomposition methods to solve a larger problem. The problem decomposition deals with breaking down the larger problem into a number of smaller sub-problems depending on their method. Different problem decomposition methods have their own strengths and limitations depending on the neural network used and application problem. In this paper we are introducing a new problem decomposition method known as Hidden-Neuron Level Decomposition (HNL). The HNL method is competing with established problem decomposition method in time series prediction. The results show that the proposed approach has improved the results in some benchmark data sets when compared to the standalone method and has competitive results when compared to methods from literature.Keywords: cooperative coevaluation, feed forward network, problem decomposition, neuron, synapse
Procedia PDF Downloads 3247096 Solution of Nonlinear Fractional Programming Problem with Bounded Parameters
Authors: Mrinal Jana, Geetanjali Panda
Abstract:
In this paper a methodology is developed to solve a nonlinear fractional programming problem in which the coefficients of the objective function and constraints are interval parameters. This model is transformed into a general optimization problem and relation between the original problem and the transformed problem is established. Finally the proposed methodology is illustrated through a numerical example.Keywords: fractional programming, interval valued function, interval inequalities, partial order relation
Procedia PDF Downloads 5167095 Exhaustive Study of Essential Constraint Satisfaction Problem Techniques Based on N-Queens Problem
Authors: Md. Ahsan Ayub, Kazi A. Kalpoma, Humaira Tasnim Proma, Syed Mehrab Kabir, Rakib Ibna Hamid Chowdhury
Abstract:
Constraint Satisfaction Problem (CSP) is observed in various applications, i.e., scheduling problems, timetabling problems, assignment problems, etc. Researchers adopt a CSP technique to tackle a certain problem; however, each technique follows different approaches and ways to solve a problem network. In our exhaustive study, it has been possible to visualize the processes of essential CSP algorithms from a very concrete constraint satisfaction example, NQueens Problem, in order to possess a deep understanding about how a particular constraint satisfaction problem will be dealt with by our studied and implemented techniques. Besides, benchmark results - time vs. value of N in N-Queens - have been generated from our implemented approaches, which help understand at what factor each algorithm produces solutions; especially, in N-Queens puzzle. Thus, extended decisions can be made to instantiate a real life problem within CSP’s framework.Keywords: arc consistency (AC), backjumping algorithm (BJ), backtracking algorithm (BT), constraint satisfaction problem (CSP), forward checking (FC), least constrained values (LCV), maintaining arc consistency (MAC), minimum remaining values (MRV), N-Queens problem
Procedia PDF Downloads 3567094 Explicit Iterative Scheme for Approximating a Common Solution of Generalized Mixed Equilibrium Problem and Fixed Point Problem for a Nonexpansive Semigroup in Hilbert Space
Authors: Mohammad Farid
Abstract:
In this paper, we introduce and study an explicit iterative method based on hybrid extragradient method to approximate a common solution of generalized mixed equilibrium problem and fixed point problem for a nonexpansive semigroup in Hilbert space. Further, we prove that the sequence generated by the proposed iterative scheme converge strongly to the common solution of generalized mixed equilibrium problem and fixed point problem for a nonexpansive semigroup. This common solution is the unique solution of a variational inequality problem and is the optimality condition for a minimization problem. The results presented in this paper are the supplement, extension and generalization of the previously known results in this area.Keywords: generalized mixed equilibrium problem, fixed-point problem, nonexpansive semigroup, variational inequality problem, iterative algorithms, hybrid extragradient method
Procedia PDF Downloads 4687093 Regret-Regression for Multi-Armed Bandit Problem
Authors: Deyadeen Ali Alshibani
Abstract:
In the literature, the multi-armed bandit problem as a statistical decision model of an agent trying to optimize his decisions while improving his information at the same time. There are several different algorithms models and their applications on this problem. In this paper, we evaluate the Regret-regression through comparing with Q-learning method. A simulation on determination of optimal treatment regime is presented in detail.Keywords: optimal, bandit problem, optimization, dynamic programming
Procedia PDF Downloads 4487092 A Fuzzy Programming Approach for Solving Intuitionistic Fuzzy Linear Fractional Programming Problem
Authors: Sujeet Kumar Singh, Shiv Prasad Yadav
Abstract:
This paper develops an approach for solving intuitionistic fuzzy linear fractional programming (IFLFP) problem where the cost of the objective function, the resources, and the technological coefficients are triangular intuitionistic fuzzy numbers. Here, the IFLFP problem is transformed into an equivalent crisp multi-objective linear fractional programming (MOLFP) problem. By using fuzzy mathematical programming approach the transformed MOLFP problem is reduced into a single objective linear programming (LP) problem. The proposed procedure is illustrated through a numerical example.Keywords: triangular intuitionistic fuzzy number, linear programming problem, multi objective linear programming problem, fuzzy mathematical programming, membership function
Procedia PDF Downloads 5587091 The Algorithm to Solve the Extend General Malfatti’s Problem in a Convex Circular Triangle
Authors: Ching-Shoei Chiang
Abstract:
The Malfatti’s Problem solves the problem of fitting 3 circles into a right triangle such that these 3 circles are tangent to each other, and each circle is also tangent to a pair of the triangle’s sides. This problem has been extended to any triangle (called general Malfatti’s Problem). Furthermore, the problem has been extended to have 1+2+…+n circles inside the triangle with special tangency properties among circles and triangle sides; we call it extended general Malfatti’s problem. In the extended general Malfatti’s problem, call it Tri(Tn), where Tn is the triangle number, there are closed-form solutions for Tri(T₁) (inscribed circle) problem and Tri(T₂) (3 Malfatti’s circles) problem. These problems become more complex when n is greater than 2. In solving Tri(Tn) problem, n>2, algorithms have been proposed to solve these problems numerically. With a similar idea, this paper proposed an algorithm to find the radii of circles with the same tangency properties. Instead of the boundary of the triangle being a straight line, we use a convex circular arc as the boundary and try to find Tn circles inside this convex circular triangle with the same tangency properties among circles and boundary Carc. We call these problems the Carc(Tn) problems. The CPU time it takes for Carc(T16) problem, which finds 136 circles inside a convex circular triangle with specified tangency properties, is less than one second.Keywords: circle packing, computer-aided geometric design, geometric constraint solver, Malfatti’s problem
Procedia PDF Downloads 1047090 Ubiquitous Scaffold Learning Environment Using Problem-based Learning Activities to Enhance Problem-solving Skills and Context Awareness
Authors: Noppadon Phumeechanya, Panita Wannapiroon
Abstract:
The purpose of this research is to design the ubiquitous scaffold learning environment using problem-based learning activities that enhance problem-solving skills and context awareness, and to evaluate the suitability of the ubiquitous scaffold learning environment using problem-based learning activities. We divide the research procedures into two phases. The first phase is to design the ubiquitous scaffold learning environment using problem-based learning activities, and the second is to evaluate the ubiquitous scaffold learning environment using problem-based learning activities. The sample group in this study consists of five experts selected using the purposive sampling method. We analyse data by arithmetic mean and standard deviation. The research findings are as follows; the ubiquitous scaffold learning environment using problem-based learning activities consists of three major steps, the first is preparation before learning. This prepares learners to acknowledge details and learn through u-LMS. The second is the learning process, where learning activities happen in the ubiquitous learning environment and learners learn online with scaffold systems for each step of problem solving. The third step is measurement and evaluation. The experts agree that the ubiquitous scaffold learning environment using problem-based learning activities is highly appropriate.Keywords: ubiquitous learning environment scaffolding, learning activities, problem-based learning, problem-solving skills, context awareness
Procedia PDF Downloads 4917089 Young Children’s Use of Representations in Problem Solving
Authors: Kamariah Abu Bakar, Jennifer Way
Abstract:
This study investigated how young children (six years old) constructed and used representations in mathematics classroom; particularly in problem solving. The purpose of this study is to explore the ways children used representations in solving addition problems and to determine whether their representations can play a supportive role in understanding the problem situation and solving them correctly. Data collection includes observations, children’s artifact, photographs and conversation with children during task completion. The results revealed that children were able to construct and use various representations in solving problems. However, they have certain preferences in generating representations to support their problem solving.Keywords: young children, representations, addition, problem solving
Procedia PDF Downloads 4507088 Two-Stage Approach for Solving the Multi-Objective Optimization Problem on Combinatorial Configurations
Authors: Liudmyla Koliechkina, Olena Dvirna
Abstract:
The statement of the multi-objective optimization problem on combinatorial configurations is formulated, and the approach to its solution is proposed. The problem is of interest as a combinatorial optimization one with many criteria, which is a model of many applied tasks. The approach to solving the multi-objective optimization problem on combinatorial configurations consists of two stages; the first is the reduction of the multi-objective problem to the single criterion based on existing multi-objective optimization methods, the second stage solves the directly replaced single criterion combinatorial optimization problem by the horizontal combinatorial method. This approach provides the optimal solution to the multi-objective optimization problem on combinatorial configurations, taking into account additional restrictions for a finite number of steps.Keywords: discrete set, linear combinatorial optimization, multi-objective optimization, Pareto solutions, partial permutation set, structural graph
Procedia PDF Downloads 1637087 On Optimum Stratification
Authors: M. G. M. Khan, V. D. Prasad, D. K. Rao
Abstract:
In this manuscript, we discuss the problem of determining the optimum stratification of a study (or main) variable based on the auxiliary variable that follows a uniform distribution. If the stratification of survey variable is made using the auxiliary variable it may lead to substantial gains in precision of the estimates. This problem is formulated as a Nonlinear Programming Problem (NLPP), which turn out to multistage decision problem and is solved using dynamic programming technique.Keywords: auxiliary variable, dynamic programming technique, nonlinear programming problem, optimum stratification, uniform distribution
Procedia PDF Downloads 3247086 Genetic Algorithm for Solving the Flexible Job-Shop Scheduling Problem
Authors: Guilherme Baldo Carlos
Abstract:
The flexible job-shop scheduling problem (FJSP) is an NP-hard combinatorial optimization problem, which can be applied to model several applications in a wide array of industries. This problem will have its importance increase due to the shift in the production mode that modern society is going through. The demands are increasing and for products personalized and customized. This work aims to apply a meta-heuristic called a genetic algorithm (GA) to solve this problem. A GA is a meta-heuristic inspired by the natural selection of Charles Darwin; it produces a population of individuals (solutions) and selects, mutates, and mates the individuals through generations in order to find a good solution for the problem. The results found indicate that the GA is suitable for FJSP solving.Keywords: genetic algorithm, evolutionary algorithm, scheduling, flexible job-shop scheduling
Procedia PDF Downloads 1447085 Number Sense Proficiency and Problem Solving Performance of Grade Seven Students
Authors: Laissa Mae Francisco, John Rolex Ingreso, Anna Krizel Menguito, Criselda Robrigado, Rej Maegan Tuazon
Abstract:
This study aims to determine and describe the existing relationship between number sense proficiency and problem-solving performance of grade seven students from Victorino Mapa High School, Manila. A paper pencil exam containing of 50-item number sense test and 5-item problem-solving test which measures their number sense proficiency and problem-solving performance adapted from McIntosh, Reys, and Bana were used as the research instruments. The data obtained from this study were interpreted and analyzed using the Pearson – Product Moment Coefficient of Correlation to determine the relationship between the two variables. It was found out that students who were low in number sense proficiency tend to be the students with poor problem-solving performance and students with medium number sense proficiency are most likely to have an average problem-solving performance. Likewise, students with high number sense proficiency are those who do excellently in problem-solving performance.Keywords: number sense, performance, problem solving, proficiency
Procedia PDF Downloads 4297084 Incorporating Polya’s Problem Solving Process: A Polytechnic Mathematics Module Case Study
Authors: Pei Chin Lim
Abstract:
School of Mathematics and Science of Singapore Polytechnic offers a Basic Mathematics module to students who did not pass GCE O-Level Additional Mathematics. These students are weaker in Mathematics. In particular, they struggle with word problems and tend to leave them blank in tests and examinations. In order to improve students’ problem-solving skills, the school redesigned the Basic Mathematics module to incorporate Polya’s problem-solving methodology. During tutorial lessons, students have to work through learning activities designed to raise their metacognitive awareness by following Polya’s problem-solving process. To assess the effectiveness of the redesign, students’ working for a challenging word problem in the mid-semester test were analyzed. Sixty-five percent of students attempted to understand the problem by making sketches. Twenty-eight percent of students went on to devise a plan and implement it. Only five percent of the students still left the question blank. These preliminary results suggest that with regular exposure to an explicit and systematic problem-solving approach, weak students’ problem-solving skills can potentially be improved.Keywords: mathematics education, metacognition, problem solving, weak students
Procedia PDF Downloads 1547083 An Optimization Model for Maximum Clique Problem Based on Semidefinite Programming
Authors: Derkaoui Orkia, Lehireche Ahmed
Abstract:
The topic of this article is to exploring the potentialities of a powerful optimization technique, namely Semidefinite Programming, for solving NP-hard problems. This approach provides tight relaxations of combinatorial and quadratic problems. In this work, we solve the maximum clique problem using this relaxation. The clique problem is the computational problem of finding cliques in a graph. It is widely acknowledged for its many applications in real-world problems. The numerical results show that it is possible to find a maximum clique in polynomial time, using an algorithm based on semidefinite programming. We implement a primal-dual interior points algorithm to solve this problem based on semidefinite programming. The semidefinite relaxation of this problem can be solved in polynomial time.Keywords: semidefinite programming, maximum clique problem, primal-dual interior point method, relaxation
Procedia PDF Downloads 2157082 A New Graph Theoretic Problem with Ample Practical Applications
Authors: Mehmet Hakan Karaata
Abstract:
In this paper, we first coin a new graph theocratic problem with numerous applications. Second, we provide two algorithms for the problem. The first solution is using a brute-force techniques, whereas the second solution is based on an initial identification of the cycles in the given graph. We then provide a correctness proof of the algorithm. The applications of the problem include graph analysis, graph drawing and network structuring.Keywords: algorithm, cycle, graph algorithm, graph theory, network structuring
Procedia PDF Downloads 3787081 Teaching and Learning Physics via GPS and WikiS
Authors: Hashini E. Mohottala
Abstract:
We report the combine use of Wikispaces (WikiS) and Group Problem Solving (GPS) sessions conducted in the introductory level physics classes. As a part of this new teaching tool, some essay type problems were posted on the WikiS in weekly basis and students were encouraged to participate in problem solving without providing numerical final answers but the steps. Wikispace is used as a platform for students to meet online and create discussions. Each week students were further evaluated on problem solving skills opening up more opportunity for peer interaction through GPS. Each group was given a different problem to solve and the answers were graded. Students developed a set of skills in decision-making, problem solving, communication, negotiation, critical and independent thinking and teamwork through the combination of WikiS and GPS.Keywords: group problem solving (GPS), wikispace (WikiS), physics education, learning
Procedia PDF Downloads 4127080 Comparative Analysis of Two Different Ant Colony Optimization Algorithm for Solving Travelling Salesman Problem
Authors: Sourabh Joshi, Tarun Sharma, Anurag Sharma
Abstract:
Ant Colony Optimization is heuristic Algorithm which has been proven a successful technique applied on number of combinatorial optimization problems. Two variants of Ant Colony Optimization algorithm named Ant System and Max-Min Ant System are implemented in MATLAB to solve travelling Salesman Problem and the results are compared. In, this paper both systems are analyzed by solving the some Travelling Salesman Problem and depict which system solve the problem better in term of cost and time.Keywords: Ant Colony Optimization, Travelling Salesman Problem, Ant System, Max-Min Ant System
Procedia PDF Downloads 4727079 On the Application of Heuristics of the Traveling Salesman Problem for the Task of Restoring the DNA Matrix
Authors: Boris Melnikov, Dmitrii Chaikovskii, Elena Melnikova
Abstract:
The traveling salesman problem (TSP) is a well-known optimization problem that seeks to find the shortest possible route that visits a set of points and returns to the starting point. In this paper, we apply some heuristics of the TSP for the task of restoring the DNA matrix. This restoration problem is often considered in biocybernetics. For it, we must recover the matrix of distances between DNA sequences if not all the elements of the matrix under consideration are known at the input. We consider the possibility of using this method in the testing of distance calculation algorithms between a pair of DNAs to restore the partially filled matrix.Keywords: optimization problems, DNA matrix, partially filled matrix, traveling salesman problem, heuristic algorithms
Procedia PDF Downloads 1447078 Transfer Knowledge From Multiple Source Problems to a Target Problem in Genetic Algorithm
Authors: Terence Soule, Tami Al Ghamdi
Abstract:
To study how to transfer knowledge from multiple source problems to the target problem, we modeled the Transfer Learning (TL) process using Genetic Algorithms as the model solver. TL is the process that aims to transfer learned data from one problem to another problem. The TL process aims to help Machine Learning (ML) algorithms find a solution to the problems. The Genetic Algorithms (GA) give researchers access to information that we have about how the old problem is solved. In this paper, we have five different source problems, and we transfer the knowledge to the target problem. We studied different scenarios of the target problem. The results showed combined knowledge from multiple source problems improves the GA performance. Also, the process of combining knowledge from several problems results in promoting diversity of the transferred population.Keywords: transfer learning, genetic algorithm, evolutionary computation, source and target
Procedia PDF Downloads 132