Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Adaptive genetic annealing calculation method for solving zero-one knapsack problem

A technology of genetic annealing and calculation method, which is applied in the field of adaptive genetic annealing calculation to solve the 0-1 knapsack problem, can solve problems such as premature convergence and convergence speed, and achieve the effects of improving convergence speed, improving search efficiency, and expanding search range

Inactive Publication Date: 2013-02-13
SHANGHAI UNIVERSITY OF ELECTRIC POWER
View PDF2 Cites 10 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0005] The present invention aims at the problems of premature convergence and slow convergence speed of the standard genetic algorithm, and proposes an adaptive genetic annealing calculation method for solving the 0-1 knapsack problem, which has the advantages of high convergence speed, optimization ability and stability, especially Suitable for solving high-dimensional constrained optimization problems

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Adaptive genetic annealing calculation method for solving zero-one knapsack problem
  • Adaptive genetic annealing calculation method for solving zero-one knapsack problem
  • Adaptive genetic annealing calculation method for solving zero-one knapsack problem

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0023] Such as figure 1 The flowchart of the adaptive genetic annealing calculation method for solving the 0-1 knapsack problem is shown, including the following steps:

[0024] 1) Set algorithm parameters, including population size popsize, chromosome length chromlong, annealing initial temperature T0, annealing coefficient k, etc.;

[0025] 2) Generate the initial population pop(0);

[0026] 3) Evaluate the fitness value of each individual in the group according to the fitness function, and judge whether it meets the optimization criteria, if so, output the best individual and the optimal solution it represents, and end the calculation; otherwise, perform the following steps;

[0027] a) Carry out genetic operations, the selection strategy adopts roulette and the optimal preservation strategy, the optimal preservation number is set to 2, the crossover and mutation operations adopt adaptive crossover and mutation probability, and generate the SA initial population sa-pop;

...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention relates to an adaptive genetic annealing calculation method for solving a zero-one knapsack problem. The algorithm adopts a selection mechanism combining roulette and an optimal storage strategy, so that the current optimal individuals are always kept in a group; by the adaptive intersection and variation probability, the group search range is expanded, then a simulated annealing algorithm is introduced, and the convergence speed of an iterative later-stage algorithm is increased; and finally, the improved adaptive genetic annealing algorithm is applied to a zero / one knapsack. An experiment result indicates that by the adaptive genetic annealing algorithm, a more satisfactory effect than that of a standard genetic algorithm and that of the conventional adaptive genetic algorithm can be achieved. The adaptive genetic annealing calculation method has the advantages of high convergence speed, high optimizing capacity and high stability, and is particularly suitable for achieving an effect of high-dimension constraint optimization.

Description

technical field [0001] The present invention relates to one, in particular to one. Background technique [0002] 0-1 knapsack: Given a bag with a load of w, n items whose weight is w i , with value v i , 1<=i<=n, Requirement: put the items into the backpack, and maximize the value of the items in the bag. In the 0-1 knapsack problem, the object is either put into the knapsack, or it is not put into the knapsack, there are only two choices. Solving which items to take out can make the items in the backpack the most valuable without exceeding the capacity of the backpack. [0003] The 0-1 Knapsack Problem (Zero-one Knapsack Problem, referred to as ZKP) is a typical NP (Non.deterministic Polynomia) complete problem in operations research, that is, a non-deterministic problem with polynomial complexity. For difficult problems, the implication is that as long as there is a polynomial time algorithm for an NP-complete problem, then the entire NP class of problems has a p...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06N3/12
Inventor 吕学勤陈树果姜英杰段利伟
Owner SHANGHAI UNIVERSITY OF ELECTRIC POWER
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com