CN109343966B - Cluster organization method and device for unmanned nodes - Google Patents
Cluster organization method and device for unmanned nodes Download PDFInfo
- Publication number
- CN109343966B CN109343966B CN201811294450.0A CN201811294450A CN109343966B CN 109343966 B CN109343966 B CN 109343966B CN 201811294450 A CN201811294450 A CN 201811294450A CN 109343966 B CN109343966 B CN 109343966B
- Authority
- CN
- China
- Prior art keywords
- unmanned
- task
- node
- initial
- fitness function
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/12—Computing arrangements based on biological models using genetic models
- G06N3/126—Evolutionary algorithms, e.g. genetic algorithms or genetic programming
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Health & Medical Sciences (AREA)
- Life Sciences & Earth Sciences (AREA)
- Biophysics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Bioinformatics & Computational Biology (AREA)
- Evolutionary Biology (AREA)
- Physiology (AREA)
- Genetics & Genomics (AREA)
- Artificial Intelligence (AREA)
- Biomedical Technology (AREA)
- Computational Linguistics (AREA)
- Data Mining & Analysis (AREA)
- Evolutionary Computation (AREA)
- General Health & Medical Sciences (AREA)
- Molecular Biology (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
本发明公开了一种无人节点的集群组织方法及装置，涉及计算机领域。该方法包括：当确定满足任务约束的无人节点的数量为零时，根据适应度函数确定每个初始个体的第一适应度函数值和第二适应度函数值，根据轮盘赌旋转法得到第一复制种群；根据所述第一适应度函数值排序的初始个体，将第一复制种群内包括的多个第一复制个体进行交叉得到交叉个体；根据变异概率选择至少两个交叉个体进行变异，并确定变异个体的第三适应度函数值；当确定迭代次数达到设定值时，将最大的所述第三适应度函数值的所述变异个体确定为最优结果，当确定所述最优结果的基因编码为1时，确定与所述最优结果对应的无人节点加入任务联盟。
The invention discloses a cluster organization method and device for unmanned nodes, and relates to the field of computers. The method includes: when it is determined that the number of unmanned nodes satisfying the task constraint is zero, determine the first fitness function value and the second fitness function value of each initial individual according to the fitness function, and obtain according to the roulette rotation method The first replication population; according to the initial individuals sorted by the first fitness function value, the multiple first replication individuals included in the first replication population are crossed to obtain cross individuals; according to the mutation probability, at least two cross individuals are selected for mutation , and determine the third fitness function value of the mutated individual; when it is determined that the number of iterations reaches the set value, the mutated individual with the largest third fitness function value is determined as the optimal result, and when the maximum is determined When the gene code of the optimal result is 1, it is determined that the unmanned node corresponding to the optimal result joins the mission alliance.
Description
Technical Field
The invention relates to the field of computers, in particular to a cluster organization method and a cluster organization device for unmanned nodes.
Background
The unmanned node refers to a single unmanned system comprising an unmanned aerial vehicle, a robot, an unmanned vehicle and the like, and has certain communication, perception, autonomous action and group cooperation capacity. The unmanned node group is composed of a large number of unmanned nodes, has planning, self-organizing and group cooperation capabilities, and is oriented to a parallel multitask cluster system. At present, research on unmanned node clusters mainly relates to problems of task allocation, cooperative algorithm, cluster communication and the like. However, there is little and little research on the organization problem of large-scale unmanned node clusters. With the increasing of the number of nodes in the unmanned node cluster and the dynamic change of the task scene, the difficulties of communication, control, decision and the like of the unmanned node cluster are increased, so that the problem of task-oriented unmanned node cluster organization is very important.
Parallel task-driven unmanned node group organization refers to organization of different unmanned nodes to cooperatively complete multiple tasks according to capabilities and resources of the different unmanned nodes. For the task-driven cluster organization problem, the current solution includes: 1) The method based on roles has the core idea that: the method comprises the following steps that an organization manager divides tasks, a role set is established, a role consists of three elements, namely sub-goals, capacity requirements and benefits, then role recruitment is carried out, an unmanned node proposes a role to be assumed, the organization manager determines the attribution of the role, and finally the organization manager organizes the unmanned nodes to complete the respective sub-goals; 2) The auction-based method has the core idea that: the method comprises the steps that an organization manager divides tasks and issues a plurality of task bidding documents for auction, the task bidding documents comprise four elements of task time, location, capability requirements and constraint, unmanned nodes evaluate the bidding documents, bid information containing task fitness is submitted, an organization manager determines auction results, and finally the organization manager organizes the unmanned nodes to complete respective tasks.
The two methods have several common problems, one is that the unmanned node may not be able to complete the subtasks independently, and the tasks need to be divided into small enough; secondly, the role and the bidding information are difficult to depict and implement, and are difficult to be suitable for the practical application scene; thirdly, under the condition of large scale, the organization efficiency is low, and the application of the large-scale unmanned node cluster is difficult to support.
Disclosure of Invention
The embodiment of the invention provides a cluster organization method and device of unmanned nodes, which are used for solving the problems that the unmanned nodes cannot complete subtasks, are difficult to be suitable for practical application scenes and have low organization efficiency in parallel task driving in the prior art.
The embodiment of the invention provides a cluster organization method of an unmanned node, which comprises the following steps:
when the number of the unmanned nodes meeting the task constraint is determined to be zero, setting an initial population comprising a plurality of initial individuals, wherein the initial individuals are gene codes comprising a multi-bit binary system; determining a first fitness function value and a second fitness function value of each initial individual according to a fitness function, and selecting a plurality of initial individuals from the initial population according to a roulette rotation method to obtain a first copy population;
crossing a plurality of first copy individuals included in the first copy population through the crossing probability and the initial individuals sorted according to the first fitness function value to obtain a plurality of crossed individuals; selecting at least two crossed individuals from the plurality of crossed individuals according to the variation probability for variation, and determining a third fitness function value of the varied individuals;
and when determining that the iteration number reaches a set value, determining the variant individual with the maximum third fitness function value as an optimal result, and when determining that the gene code of the optimal result is 1, determining that the unmanned node corresponding to the optimal result joins a task alliance.
Preferably, the method further comprises the following steps:
when the number of the unmanned nodes meeting the task constraint is determined to be multiple, determining the capability exceeding degree of the multiple unmanned nodes, and determining the unmanned node with the lowest exceeding degree as a first unmanned node; wherein the first unmanned node is responsible for tasks with the task constraints;
determining the capability overrun of the unmanned node by the following formula:
CS＝CL+CP
CP＝(||perception Ni ||-||perception T ||)*w 2
wherein CL denotes the degree of excess of the load capacity, load Ni Representing the loadability value, load, of the unmanned node T Representing the demand value of the task on the load capacity, CP representing the excess of the perception capacity, | permission Ni | l represents the total number of the sensing ability of the unmanned node, and | permission T | | represents the total number of the tasks required by the sensing capability, and Nodes = { N = i |i＝{1,2,3,...n}}，Tasks＝{T i |i＝{1,2,3,...m}}，w 1 Weight, w, representing the degree of excess of load capacity 2 A weight representing the degree of excess of the perception capability.
Preferably, the unmanned node is described by a quintuple group:
Unmanned-Node＝＜U id ，Type，Capability，Location，State＞
describing the task by adopting a quadruplet:
Task＝＜T id ，Location，Time，Capability＞
wherein, U id The method comprises the steps that the ID of an unmanned node is represented, the Type represents the Type of the unmanned node, the Capability represents the Capability of the unmanned node, the Location represents the maximum load Capability of the unmanned node, and the State represents the State of the current unmanned node; t is a unit of id Indicating the task ID, location indicating the spatial Location information of the task, time indicating the Time constraint of the task, capability indicating the Capability requirement of the task.
Preferably, the determining a first fitness function value and a second fitness function value of each initial individual according to a fitness function specifically includes:
determining a first fitness function value for the initial individual by:
f(Q)＝cost(Q)+r 1 *P(Q)+r 2 *|H(Q)|
determining a second fitness function value for the initial individual by:
newf(Q i )＝maxValue＝max(f(Q i ))+100
after the first fitness function value and the second fitness function value of each initial individual are determined according to the fitness function, the method further includes:
determining the selection probability of the initial individual and the cumulative probability of the initial individual by the following formulas, respectively:
wherein f (Q) represents the fitness of the initial individual Q, cost (Q) represents the cost of the initial individual Q, P (Q) represents the penalty value of the initial individual Q in terms of load capacity, H (Q) represents the penalty value of the initial individual Q in terms of perception capacity, and newf (Q) i ) A second fitness function value, P (Q), of said initial individual i ) For the selection probability of the initial individual, sum (Q) i ) Is the cumulative probability of the initial individual, r 1 Weight, r, representing a penalty value for the load capacity 2 A weight representing a perceptual penalty value.
Preferably, after determining that the unmanned node corresponding to the optimal result joins the task alliance, the method further comprises:
when only one unmanned node is included in the task alliance, determining that the unmanned node is an administrator of the task alliance; or
When the task alliance comprises a plurality of unmanned nodes, determining the unmanned node with the maximum capability value as an administrator of the task alliance according to the capability value;
the formula for the capability value is as follows:
score i ＝{load i |perception i |}·{U 1 U 2 } T
wherein, load represents the load capacity of the unmanned node, | permission | represents the number of the perception capacity of the unmanned node, U 1 Weight, U, representing the load capacity 2 A weight representing the perception capability.
An embodiment of the present invention further provides a cluster organization apparatus for an unmanned node, including:
an obtaining unit, configured to set an initial population including a plurality of initial individuals when it is determined that the number of unmanned nodes satisfying the task constraint is zero, the initial individuals being a gene code including a multi-bit binary; determining a first fitness function value and a second fitness function value of each initial individual according to a fitness function, and selecting a plurality of initial individuals from the initial population according to a roulette rotation method to obtain a first copy population;
a first determining unit, configured to cross, through a cross probability and the initial individuals sorted according to the first fitness function value, a plurality of first replication individuals included in the first replication population to obtain a plurality of crossed individuals; selecting at least two crossed individuals from the plurality of crossed individuals according to the variation probability for variation, and determining a third fitness function value of the varied individuals;
and the second determining unit is used for determining the variant individual with the maximum third fitness function value as an optimal result when the iteration number is determined to reach a set value, and determining that the unmanned node corresponding to the optimal result joins the task alliance when the gene code of the optimal result is determined to be 1.
Preferably, the method further comprises the following steps: a third determining unit, configured to determine, when it is determined that the number of the unmanned nodes satisfying the task constraint is multiple, a capability excess degree of the multiple unmanned nodes, and determine the unmanned node with the lowest excess degree as the first unmanned node; wherein the first unmanned node is responsible for tasks subject to the task constraints;
determining the capability overrun of the unmanned node by the following formula:
CS＝CL+CP
CP＝(||perception Ni ||-||perception T ||)*w 2
wherein CL denotes the degree of excess of the load capacity, load Ni Representing the load capacity value, load, of the unmanned node T Representing the demand value of the task on the load capacity, CP representing the excess of the perception capacity, | permission Ni I represents the total number of the sensing ability of the unmanned node, and I success represents the total number of the sensing ability of the unmanned node T I represents the total number of the tasks required by the sensing capability, and Nodes = { N = |) i |i＝{1,2,3,...n}}，Tasks＝{T i I = {1,2,3,. M } }, w1 represents the weight of the load capacity exceeding degree 2 A weight indicating how much the perception capability is out of level.
Preferably, the unmanned node is described by a quintuple group:
Unmanned-Node＝＜U id ，Type，Capability，Location，State＞
describing the task by adopting a quadruplet:
Task＝＜T id ，Location，Time，Capability＞
wherein, U id The method comprises the steps of representing the ID of an unmanned node, type representing the Type of the unmanned node, capability representing the Capability of the unmanned node, location representing the maximum load Capability of the unmanned node, and State representing the State of the current unmanned node; t is id Indicating the task ID, location indicating the spatial Location information of the task, time indicating the Time constraint of the task, capability indicating the Capability requirement of the task.
Preferably, the first determining unit is specifically configured to:
determining a first fitness function value for the initial individual by:
f(Q)＝cost(Q)+r 1 *P(Q)+r 2 *|H(Q)|
determining a second fitness function value for the initial individual by:
newf(Q i )＝maxValue＝max(f(Q i ))+100
after the first fitness function value and the second fitness function value of each initial individual are determined according to the fitness function, the method further includes:
determining the selection probability of the initial individual and the cumulative probability of the initial individual by the following formulas, respectively:
wherein f (Q) represents the fitness of the initial individual Q, cost (Q) represents the cost of the initial individual Q, P (Q) represents the penalty value of the initial individual Q in terms of load capacity, H (Q) represents the penalty value of the initial individual Q in terms of perception capacity, and newf (Q) i ) A second fitness function value, P (Q), of the initial individual i ) For the selection probability of the initial individual, sum (Q) i ) Is the cumulative probability of the initial individual.
Preferably, the second determination unit is further configured to:
when only one unmanned node is included in the task alliance, determining that the unmanned node is an administrator of the task alliance; or
When the task alliance comprises a plurality of unmanned nodes, determining the unmanned node with the maximum capability value as an administrator of the task alliance according to the capability value;
the formula for the capability value is as follows:
score i ＝{load i |perception i |}·{U 1 U 2 } T
wherein, loadRepresenting the load capacity of the unmanned node, | permission | representing the number of the perception capacities of the unmanned node, U 1 Weight, U, representing the load capacity 2 A weight representing the perception capability.
The embodiment of the invention provides a cluster organization method of an unmanned node, which comprises the following steps: when the number of the unmanned nodes meeting the task constraint is determined to be zero, setting an initial population comprising a plurality of initial individuals, wherein the initial individuals are gene codes comprising multi-bit binary systems; determining a first fitness function value and a second fitness function value of each initial individual according to a fitness function, and selecting a plurality of initial individuals from the initial population according to a roulette rotation method to obtain a first copy population; crossing a plurality of first replication individuals included in the first replication population through the crossing probability and the initial individuals sorted according to the first fitness function value to obtain a plurality of crossed individuals; selecting at least two crossed individuals from the plurality of crossed individuals according to the variation probability for variation, and determining a third fitness function value of the varied individuals; and when determining that the iteration number reaches a set value, determining the variant individual with the maximum third fitness function value as an optimal result, and when determining that the gene code of the optimal result is 1, determining that the unmanned node corresponding to the optimal result joins a task alliance. According to the method, when no unmanned node meeting the task requirement is confirmed, one or more unmanned nodes can be selected for the task through a genetic algorithm, so that the problems that the existing parallel task drive has the defects that the unmanned nodes cannot complete sub-tasks, are difficult to adapt to practical application scenes and have low organization efficiency are solved.
Drawings
In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings used in the description of the embodiments or the prior art will be briefly described below, it is obvious that the drawings in the following description are only some embodiments of the present invention, and for those skilled in the art, other drawings can be obtained according to the drawings without creative efforts.
Fig. 1 is a schematic flow chart of a cluster organization method for an unmanned node according to an embodiment of the present invention;
fig. 2 is a schematic flowchart of a method for confirming that an unmanned node meets task constraints according to an embodiment of the present invention;
FIG. 3 is a schematic diagram showing the selection of two gene positions for a replicating individual 1 and a replicating individual 2 according to an embodiment of the present invention;
FIG. 4 is a schematic diagram of a task federation structure provided in an embodiment of the present invention;
fig. 5 is a schematic structural diagram of a cluster organization apparatus of an unmanned node according to an embodiment of the present invention.
Detailed Description
The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are only a part of the embodiments of the present invention, and not all of the embodiments. All other embodiments, which can be obtained by a person skilled in the art without making any creative effort based on the embodiments in the present invention, belong to the protection scope of the present invention.
Fig. 1 exemplarily shows a schematic flow chart of a cluster organization method for an unmanned node according to an embodiment of the present invention, and as shown in fig. 1, the method mainly includes the following steps:
and 103, when the iteration number is determined to reach a set value, determining the variant individual with the maximum third fitness function value as an optimal result, and when the gene code of the optimal result is determined to be 1, determining that the unmanned node corresponding to the optimal result joins in a task alliance.
In the embodiment of the invention, the unmanned node and the task are formally described respectively, specifically, the unmanned node is formally described by adopting a quintuple group, and the task is formally described by adopting a quadruplet group.
1. And formalized description is carried out on the unmanned node by adopting a quintuple:
Unmanned-Node＝＜U id ，Type，Capability，Location，State＞
wherein, U id An ID representing an unmanned node; type represents an unmanned node Type, for example, 1 represents an unmanned aerial vehicle, 2 represents an unmanned vehicle, and 3 represents a robot; capability represents the capabilities of the unmanned node, and the Capability may be represented by a triplet; location represents the maximum load capacity of the unmanned node, and State represents the State of the current unmanned node;
specifically, the triplets of Capability may be represented as:
Capability＝＜Power,Loads，Perception＞
wherein, power = < Battery, max-endplay > represents endurance capacity, and represents electric quantity and maximum endurance time respectively; loads represent the maximum load capacity of the unmanned node, and gram is taken as a standard;
perception = [ < sensor, max-range, min-range, rate, precision >, ] represents the perceptual capability,
sensor denotes the sensor type, max - range and min - range represents the maximum and minimum perception ranges, rate represents frequency, and precision represents perception accuracy;
2. formalized description of tasks using quaternions
Task＝＜T id ，Location，Time，Capability＞
Wherein, T id Represents a task ID;
location = < x, y, z, radius, width, length > represents spatial position information of the task, and parameters respectively represent task coordinates and an area range; time = < LST, LFT > represents Time constraint of the task, representing latest start Time, latest completion Time, respectively; capability = < Loads, permission > represents Capability requirement of the task, and represents load Capability and Perception Capability respectively, and the specific description is the same as that of the load and Perception Capability in the unmanned node.
Table 1 is a detailed description of the unmanned nodes and tasks:
TABLE 1 description of unmanned nodes and tasks
Before step 101, assuming that there are m groups of tasks and n unmanned nodes currently, for each task, one or more unmanned nodes are selected for the task by using an unmanned node method for confirming that the task constraint is satisfied as shown in fig. 2, and a federation is formed by the several unmanned nodes and is responsible for executing the task.
Wherein, the unmanned node can be expressed as: nodes = { N = i |i＝{1，2，3，...n}}；
The task may be represented as: tasks = { T = i |i＝1，2，3，...n}；
Specifically, as shown in fig. 2:
step 201, selecting an unmanned node meeting task capacity requirements from the current idle unmanned nodes, wherein the capacity of the candidate unmanned node is greater than or contains the capacity requirements of the task;
step 202, if only one unmanned node is satisfied, selecting the node;
step 203, if there are multiple unmanned nodes, calculating the capability excess degree of each candidate unmanned node according to the following formula, and determining the unmanned node with the lowest excess degree as the first unmanned node.
In the embodiment of the present invention, the capability excess degree of the unmanned node is determined by the following formula (1):
CS＝CL+CP (1)
where CL represents the excess of the load capacity and CP represents the excess of the sensing capacity.
Specifically, the degree of excess of the load capacity is determined by the following formula (2), and the degree of excess of the sensing capacity is determined by the following formula (3):
CP＝(||perception Ni ||-||perception T ||)*w 2 (3)
wherein, load Ni Representing the load capacity value, load, of the unmanned node T Represents the task's requirement value for load capacity, | permission Ni I represents the total number of the sensing ability of the unmanned node, and I success represents the total number of the sensing ability of the unmanned node T | | represents the total number of the tasks required by the sensing capability, and Nodes = { N = i |i＝{1,2,3,...n}}，Tasks＝{T i |i＝{1,2,3,...m}}，w 1 Weight, w, representing the degree of excess of load capacity 2 A weight indicating how much the perception capability is out of level.
In the embodiment of the invention, when the capability of the unmanned node exceeds the minimum degree, the unmanned node is determined as the first node, and the first node is used for being responsible for the task.
When none of the unmanned nodes can meet the task constraint requirement, step 204, then the unmanned node or nodes need to be selected to be responsible for the task through the following steps 101, 102 and 103.
Before step 101, several related concepts need to be introduced:
1. gene coding:
using binary coding of n bitsDefining a coalition of individuals Q, Q = { a = { 1 ，a 2 ，...，a n }, gene a i =1, denotes an unmanned node N i Join the task alliance, otherwise, a i =0 denotes an unmanned node N i No join task federation is added.
Examples are: q = {0,1, 0,1}, which means that the unmanned nodes 2,3, 5 join the federation, and the unmanned nodes 1, 4 do not join.
2. Fitness function design
f(Q)＝cost(Q)+r 1 *P(Q)+r 2 *|H(Q)| (3)
Wherein f (Q) represents the fitness of the individual Q, cost (Q) represents the cost of the individual Q, P (Q) represents the penalty value of the individual Q in terms of load capacity, H (Q) represents the penalty value of the individual Q in terms of perception capacity, r (Q) represents the fitness of the individual Q 1 Weight, r, representing a penalty value for the load capacity 2 A weight representing a perceptual penalty value.
Wherein, X T 、Y T 、Z T Coordinates X, Y, Z, X representing the position of the task T area, respectively Ni 、Y Ni 、Z Ni Respectively represent unmanned nodes N i Position coordinates X, Y, Z; load Ni Representing the load capacity value, load, of the unmanned node T Representing the task's demand value for load capacity.
Wherein b = | | duration T ||，||perception T I represents the total number of tasks required for perception, c i Indicating the task's need for some perceptual capability (e.g. the task needs camera capability, c) i Is imaging capability), therefore, the permission T (c i )＝1，perception T (c i ) Indicating whether the individual Q has a perceptual capability c i 。
In the embodiment of the present invention, the lower the fitness value f (Q), the better the individual, i.e., the better the federation result represented by the individual.
In step 101, following step 204, when it is determined that the number of unmanned nodes satisfying the task constraint is zero, an initial population including a plurality of initial individuals is set, where the population size is S and the maximum number of iterations is L. In the embodiment of the invention, the initial individual is a gene code comprising a multi-bit binary system, and when the gene code is 1, the initial individual corresponding to the gene code is an unmanned node capable of joining a task alliance; when the gene code is 0, it means that the initial individual corresponding to the gene code is an unmanned node incapable of joining the task alliance.
For example, if a plurality of initial individuals are included in the initial population, a set threshold P (P e (0, 1)) can be set for each initial individual, and then a number q (q e [0,1 ]) can be randomly generated]) When p.ltoreq.q, the gene a of the initial individual Q can be determined i =1, i.e. it means that the initial individual corresponding to the gene code is an unmanned node capable of joining task alliance, otherwise, when a i And if the number is not less than 0, the initial individual corresponding to the gene code is an unmanned node which cannot join the task alliance.
Further, determining a first fitness of each initial individual included in the initial population according to a formula (3), wherein in practical application, if the first fitness is higher, the probability of being selected is higher; in the embodiment of the present invention, since it is defined that the lower the fitness function value is, the better the result is, therefore, the existing roulette selection method needs to be processed in one step, specifically as follows:
after the first fitness of each initial individual included in the initial population is confirmed, the first fitness of a plurality of initial individuals is ranked, and the maximum value of the first fitness is selected; and (4) processing the selected maximum value according to the following formula (9), so that the second fitness of the initial individual can be obtained.
Specifically, equation (9) is as follows:
newf(Q i )＝maxValue-f(Q i )＝max(f(Q i ))+100-f(Q i )
wherein maxValue = max (f (Q) i ) +100, the second fitness of each initial individual within the initial population may be determined by equation (9) as: { maxValue-f (Q) 1 )，maxValue-f(Q 2 )，maxValue-f(Q 3 ),...,maxValue-f(Q s ) It can be simply written as: { newf (Q) 1 )，newf(Q 2 )，newf(Q 3 )，...，newf(Q s )}。
Further, after the second fitness of the initial individuals is confirmed, the selection probability of each initial individual and the cumulative probability of the initial individual may also be determined according to the following formulas:
wherein f (Q) represents the fitness of the individual Q, cost (Q) represents the cost of the individual Q, P (Q) represents the penalty value of the individual Q in terms of the load capacity, H (Q) represents the penalty value of the individual Q in terms of the perception capacity, and newf (Q) i ) A second fitness function value, P (Q), of the initial individual i ) A selection probability for the initial individual, sum (Q) i ) Is the cumulative probability, r, of the initial individual 1 Representing a loadWeight of penalty value, r 2 A weight representing a perceptual penalty value.
Further, a random number p is generated in a set interval [0,1 ], and p is in the [0,1 ]]If Sum (Q) i )≤p＜Sum(Q i+1 ) Then select the initial individual Q i+1 . Selected initial individuals are replicated so that a first replication population can be obtained.
For example, if there are four chromosomes as follows:
s1＝13(01101)
s2＝24(11000)
s3＝8(01000)
s4＝19(10011)
assuming that the second fitness of the plurality of chromosomes is:
f(s1)＝f(13)＝13^2＝169；
f(s2)＝f(24)＝24^2＝576；
f(s3)＝f(8)＝8^2＝64；
f(s4)＝f(19)＝19^2＝361；
confirming the selection probability of the chromosome according to equation (10):
confirming the cumulative probability of chromosomes according to equation (11):
if 4 random numbers are generated from the interval [0,1 ]:
r1＝0.450126，
r2＝0.110347，
r3＝0.572496，
r4＝0.98503；
the following situation can be obtained as shown in table 1 below:
| chromosome | Second degree of fitness | Probability of selection | Cumulative probability | Number of selections |
| s1＝01101 | 169 | 0.14 | 0.14 | 1 |
| s2＝11000 | 576 | 0.49 | 0.63 | 2 |
| s3＝01000 | 64 | 0.06 | 0.69 | 0 |
| s4＝10011 | 361 | 0.31 | 1.00 | 1 |
From table 1 it can be determined that chromosome s11 times, chromosome s22 times and chromosome s41 times can be selected, resulting in a first replication population.
In step 102, according to the first fitness function value, a plurality of initial individuals included in the initial population are sorted from large to small, and the replication individuals in the first replication population are respectively paired and crossed according to the sorted order, so that crossed individuals can be obtained; for example, a first and a second within a first replication population are paired and then crossed according to a crossover probability, where crossing is performed by randomly selecting two gene locations to cross. Fig. 3 is a schematic diagram illustrating that two gene positions are selected for the replication individual 1 and the replication individual 2 to cross, as shown in fig. 3, the replication individual 1 and the replication individual 2 are paired, the 2 nd position and the 5 th position are randomly selected to cross, that is, the 2 nd gene position and the 5 th gene position are selected, and the gene values of the individual 1 and the individual 2 at the two positions are interchanged to obtain two new individuals.
And further, selecting at least two crossed individuals from the multiple crossed individuals for mutation according to the mutation probability, and randomly selecting two gene positions for mutation according to the selected individuals.
And after the variant individual is determined, determining a third fitness function value of the variant individual according to the fitness function formula.
In step 103, assuming that the iteration number of the algorithm reaches the set maximum number, the algorithm stops running, so as to determine a third fitness of each variant individual, and compares the determined third fitness with the first fitness of the initial individual, and if the third fitness is greater than the first fitness, determining to select the variant individual corresponding to the third fitness; if the third fitness is smaller than the first fitness, determining to select an initial individual corresponding to the first fitness;
further, one variant individual or initial individual having the greatest fitness is selected as the optimal result from the selected variant individuals or initial individuals.
After the optimal result is determined, gene decoding needs to be carried out on the optimal result, and if the gene decoding result is 1, it is determined that the unmanned node corresponding to the optimal result can be added into the task alliance; and if the gene decoding result is 0, determining that the unmanned node corresponding to the optimal result cannot be added into the task alliance.
In the embodiment of the present invention, the number of the unmanned nodes joining the task alliance may be one, or may include a plurality of nodes. Through the algorithm, a plurality of unmanned nodes can be selected to join in the task alliance, and when the task alliance comprises a plurality of unmanned nodes, one unmanned node needs to be selected for each task alliance to serve as an administrator of the task alliance. Specifically, if only one unmanned node exists in the single-task alliance, the unmanned node is an administrator of the alliance; and determining the unmanned node with the maximum capability value as an administrator of the task alliance according to the capability values.
The formula of the capacity value is shown as (12):
score i ＝{load i |perception i |}·{U 1 U 2 } T (12)
wherein, load represents the load capacity of the unmanned node, | permission | represents the number of the perception capacity of the unmanned node, and U 1 Weight, U, representing the load capacity 2 A weight representing the perception capability.
In practical applications, if the selected unmanned node with the largest capability value is the administrator of the federation, and if there are a plurality of unmanned nodes with the same capability value, one of the unmanned nodes is randomly selected.
When all task alliance administrators have finished selecting, the unmanned node group forms the structure shown in fig. 4.
Based on the same inventive concept, embodiments of the present invention provide an unmanned node cluster organization apparatus, and as the principle of the apparatus for solving the technical problem is similar to that of an unmanned node cluster organization method, the implementation of the apparatus may refer to the implementation of the method, and the repeated parts are not described again.
Fig. 5 is a schematic structural diagram of a cluster organizing apparatus for an unmanned node according to an embodiment of the present invention, and as shown in fig. 5, the apparatus includes an obtaining unit 501, a first determining unit 502, a second determining unit 503, and a third determining unit 504.
A obtaining unit 501, configured to set an initial population including a plurality of initial individuals when it is determined that the number of unmanned nodes satisfying the task constraint is zero, where the initial individuals are gene codes including a multi-bit binary system; determining a first fitness function value and a second fitness function value of each initial individual according to a fitness function, and selecting a plurality of initial individuals from the initial population according to a roulette rotation method to obtain a first copy population;
a first determining unit 502, configured to cross a plurality of first replication individuals included in the first replication population through a cross probability and the initial individuals sorted according to the first fitness function value, so as to obtain a plurality of crossed individuals; selecting at least two crossed individuals from the plurality of crossed individuals according to the variation probability for variation, and determining a third fitness function value of the varied individuals;
a second determining unit 503, configured to determine, as an optimal result, the variant individual having the largest third fitness function value when it is determined that the number of iterations reaches a set value, and determine, when it is determined that a gene code of the optimal result is 1, that an unmanned node corresponding to the optimal result joins the task league.
Preferably, the method further comprises the following steps: a third determining unit 504, configured to determine, when it is determined that the number of the unmanned nodes satisfying the task constraint is multiple, a capability excess degree of the multiple unmanned nodes, and determine the unmanned node with the lowest excess degree as the first unmanned node; wherein the first unmanned node is responsible for tasks subject to the task constraints;
determining the capability overrun of the unmanned node by the following formula:
CS＝CL+CP
CP＝(||perception Ni ||-||perception T ||)*w 2
wherein CL denotes the degree of excess of the load capacity, load Ni Representing the load capacity value, load, of the unmanned node T Representing the task's demand value for load capacity, CP representing the excess of perception capacity, | permission Ni I represents the total number of the sensing ability of the unmanned node, and I success represents the total number of the sensing ability of the unmanned node T I represents the total number of the tasks required by the sensing capability, and Nodes = { N = |) i |i＝{1,2,3,...n}}，Tasks＝{T i I = {1,2,3,. M } }, w1 represents the weight of the load capacity exceeding degree 2 A weight indicating how much the perception capability is out of level.
Preferably, the unmanned node is described by a quintuple set:
Unmanned-Node＝＜U id ，Type，Capability，Location，State＞
describing the task by adopting a quadruplet:
Task＝＜T id ，Location，Time，Capability＞
wherein, U id The method comprises the steps that the ID of an unmanned node is represented, the Type represents the Type of the unmanned node, the Capability represents the Capability of the unmanned node, the Location represents the maximum load Capability of the unmanned node, and the State represents the State of the current unmanned node; t is id Indicating the task ID, location indicating the spatial Location information of the task, time indicating the Time constraint of the task, capability indicating the Capability requirement of the task.
Preferably, the first determining unit 502 is specifically configured to:
determining a first fitness function value for the initial individual by:
f(Q)＝cost(Q)+r 1 *P(Q)+r 2 *|H(Q)|
determining a second fitness function value for the initial individual by:
newf(Q i )＝maxValue＝max(f(Q i ))+100
after the first fitness function value and the second fitness function value of each initial individual are determined according to the fitness function, the method further includes:
determining the selection probability of the initial individual and the cumulative probability of the initial individual by the following formulas, respectively:
wherein f (Q) represents the fitness of the initial individual Q, cost (Q) represents the cost of the initial individual Q, P (Q) represents the penalty value of the initial individual Q in terms of load capacity, H (Q) represents the penalty value of the initial individual Q in terms of perception capacity, and newf (Q) i ) Second fitness function of the initial individualNumerical value, P (Q) i ) For the selection probability of the initial individual, sum (Q) i ) Is the cumulative probability, r, of the initial individual 1 Weight, r, representing a penalty value for the load capacity 2 A weight representing a perceptual penalty value.
Preferably, the second determining unit 503 is further configured to:
when only one unmanned node is included in the task alliance, determining that the unmanned node is an administrator of the task alliance; or
When the task alliance comprises a plurality of unmanned nodes, determining the unmanned node with the maximum capability value as an administrator of the task alliance according to the capability value;
the formula for the capability value is as follows:
score i ＝{load i |perception i |}·{U 1 U 2 } T
wherein, load represents the load capacity of the unmanned node, | permission | represents the number of the perception capacity of the unmanned node, U 1 Weight, U, representing the load capacity 2 A weight representing the perception capability.
It should be understood that the above cluster organization apparatus of the unmanned node includes only units that are logically divided according to the functions implemented by the device apparatus, and in practical applications, the above units may be stacked or split. The functions implemented by the cluster organizing apparatus for the unmanned node according to this embodiment correspond to the cluster organizing method for the unmanned node according to the foregoing embodiment one by one, and for a more detailed processing flow implemented by the cluster organizing apparatus, the detailed description is already described in the first method embodiment, and the detailed description is not repeated here.
As will be appreciated by one skilled in the art, embodiments of the present invention may be provided as a method, system, or computer program product. Accordingly, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present invention may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.
The present invention is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each flow and/or block of the flow diagrams and/or block diagrams, and combinations of flows and/or blocks in the flow diagrams and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
While preferred embodiments of the present invention have been described, additional variations and modifications in those embodiments may occur to those skilled in the art once they learn of the basic inventive concepts. Therefore, it is intended that the appended claims be interpreted as including preferred embodiments and all such alterations and modifications as fall within the scope of the invention.
It will be apparent to those skilled in the art that various changes and modifications may be made in the present invention without departing from the spirit and scope of the invention. Thus, if such modifications and variations of the present invention fall within the scope of the claims of the present invention and their equivalents, the present invention is also intended to include such modifications and variations.
Claims (4)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811294450.0A CN109343966B (en) | 2018-11-01 | 2018-11-01 | Cluster organization method and device for unmanned nodes |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811294450.0A CN109343966B (en) | 2018-11-01 | 2018-11-01 | Cluster organization method and device for unmanned nodes |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN109343966A CN109343966A (en) | 2019-02-15 |
| CN109343966B true CN109343966B (en) | 2023-04-07 |
Family
ID=65313273
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201811294450.0A Active CN109343966B (en) | 2018-11-01 | 2018-11-01 | Cluster organization method and device for unmanned nodes |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109343966B (en) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110321938B (en) * | 2019-06-20 | 2022-10-11 | 西北工业大学 | State space construction method and device of intelligent unmanned cluster |
| CN111007874B (en) * | 2019-09-18 | 2022-07-19 | 合肥工业大学 | Electric power inspection method and device coordinated by drone and vehicle |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104573820A (en) * | 2014-12-31 | 2015-04-29 | 中国地质大学（武汉） | Genetic algorithm for solving project optimization problem under constraint condition |
| CN105704255A (en) * | 2016-04-29 | 2016-06-22 | 浙江理工大学 | Server load balancing method based on genetic algorithm |
| WO2016165392A1 (en) * | 2015-04-17 | 2016-10-20 | 华南理工大学 | Genetic algorithm-based cloud computing resource scheduling method |
| CN106934459A (en) * | 2017-02-03 | 2017-07-07 | 西北工业大学 | A kind of self-adapted genetic algorithm based on Evolution of Population process |
| CN107329831A (en) * | 2017-06-29 | 2017-11-07 | 北京仿真中心 | A kind of artificial resource dispatching method based on improved adaptive GA-IAGA |
| WO2018036282A1 (en) * | 2016-08-24 | 2018-03-01 | 深圳市中兴微电子技术有限公司 | Task scheduling method, device and computer storage medium |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7668788B2 (en) * | 2005-06-06 | 2010-02-23 | Wren William E | Resource assignment optimization using direct encoding and genetic algorithms |
| CN102711266B (en) * | 2012-05-17 | 2014-08-13 | 北京邮电大学 | Scheduling and resource allocation joint optimization method based on genetic algorithm |
-
2018
- 2018-11-01 CN CN201811294450.0A patent/CN109343966B/en active Active
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104573820A (en) * | 2014-12-31 | 2015-04-29 | 中国地质大学（武汉） | Genetic algorithm for solving project optimization problem under constraint condition |
| WO2016165392A1 (en) * | 2015-04-17 | 2016-10-20 | 华南理工大学 | Genetic algorithm-based cloud computing resource scheduling method |
| CN105704255A (en) * | 2016-04-29 | 2016-06-22 | 浙江理工大学 | Server load balancing method based on genetic algorithm |
| WO2018036282A1 (en) * | 2016-08-24 | 2018-03-01 | 深圳市中兴微电子技术有限公司 | Task scheduling method, device and computer storage medium |
| CN106934459A (en) * | 2017-02-03 | 2017-07-07 | 西北工业大学 | A kind of self-adapted genetic algorithm based on Evolution of Population process |
| CN107329831A (en) * | 2017-06-29 | 2017-11-07 | 北京仿真中心 | A kind of artificial resource dispatching method based on improved adaptive GA-IAGA |
Non-Patent Citations (3)
| Title |
|---|
| Genetic Algorithm Based Decentralized Task Assignment for Multiple;Hyunjin Choi et al;《IJASS》;20111231;全文 * |
| 基于自适应惩罚函数的云工作流调度协同进化遗传算法;徐健锐等;《计算机科学》;20180815(第08期);全文 * |
| 无线传感器网络节点感知进化计算模型研究;孔凡兴;《计算机仿真》;20130515(第05期);全文 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN109343966A (en) | 2019-02-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109993299A (en) | Data training method and device, storage medium, electronic device | |
| CN115237592B (en) | Privacy-aware hybrid cloud service flow scheduling method | |
| CN113705812A (en) | Production scheduling method and system based on hybrid parallel inheritance and variable neighborhood algorithm | |
| CN110414569A (en) | Cluster realizing method and device | |
| CN112231466A (en) | Enterprise matching method and device in matching activities | |
| US11611599B2 (en) | System and method for grouping participant devices in a communication environment | |
| CN110334919A (en) | A kind of production line reso urce matching method and device | |
| CN109343966B (en) | Cluster organization method and device for unmanned nodes | |
| CN114461386A (en) | Task allocation method and task allocation device | |
| CN112272102A (en) | Method and device for unloading and scheduling edge network service | |
| CN113706326A (en) | Mobile social network diagram modification method based on matrix operation | |
| CN120688830A (en) | Multi-unmanned aerial vehicle collaborative task dynamic allocation method | |
| CN117573370A (en) | A hybrid parallel inference scheduling method, device, equipment and medium for heterogeneous clusters | |
| CN117170864A (en) | Resource arrangement method, system, equipment and storage medium based on virtualization platform | |
| Mohammed et al. | 3-SAT using island-based genetic algorithm | |
| CN117539587A (en) | Resource scheduling method, apparatus, computer device, storage medium and program product | |
| CN110175172B (en) | A Parallel Enumeration Method for Large Bipartite Cliques Based on Sparse Bipartite Graphs | |
| CN105005501B (en) | A kind of second order optimizing and scheduling task method towards cloud data center | |
| CN108427773B (en) | Distributed knowledge graph embedding method | |
| CN106708609A (en) | Characteristics generation method and system | |
| CN115933664B (en) | Scheduling methods and systems for logistics robots | |
| CN117892940B (en) | A method and system for optimizing emergency resource scheduling based on resource scheduling graph | |
| CN116520786B (en) | Flexible job shop scheduling method for reconfigurable manufacturing unit capabilities | |
| CN106709572A (en) | Data processing method and equipment | |
| CN119537024A (en) | Edge computing task allocation method, device, system, storage medium and product |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |