技术领域technical field
本发明涉及一种异构多核任务分配方法。特别是涉及一种群智能优化算法应用于基于异构多核模型的系统任务分配问题时的基于改进蜂群算法的异构多核任务分配方法。The invention relates to a heterogeneous multi-core task allocation method. In particular, it relates to a heterogeneous multi-core task allocation method based on an improved bee colony algorithm when a swarm intelligence optimization algorithm is applied to a system task allocation problem based on a heterogeneous multi-core model.
背景技术Background technique
1、基于异构多核模型的任务分配问题描述1. Description of task assignment based on heterogeneous multi-core model
复杂嵌入式系统往往可以表述成由多个具有不同特定结构，用来执行不同特定任务的处理器核组成。基于异构多核模型的任务分配问题可以用一个二元组表示G＝(I,R,C)表示，其中I＝{I1,I2,I3,...,Ii,...,IM|(i∈M)}表示基于异构多核模型系统中的任务单元的集合(假设共有M个任务节点)，其中Ii(i∈M)表示第i个任务节点的属性，C＝{C1,C2,C3,...,Cp,...,CN|p∈N}表示基于异构多核模型系统中的处理器核的集合(假设共有n个处理器核)，其中Cp(p∈N)表示第p个处理器核的属性，表示任意有依赖关系的i,j两个任务节点在第p,q两个处理器核间通信属性。A complex embedded system can often be described as consisting of multiple processor cores with different specific structures for performing different specific tasks. The task allocation problem based on the heterogeneous multi-core model can be represented by a two-tuple representation G=(I,R,C), where I={I1 ,I2 ,I3 ,...,Ii ,... , IM |(i∈M)} represents the set of task units based on the heterogeneous multi-core model system (assuming there are M task nodes in total), where Ii (i∈M) represents the attribute of the i-th task node, C ={C1 ,C2 ,C3 ,...,Cp ,...,CN |p∈N} represents the set of processor cores in the system based on the heterogeneous multi-core model (assuming that there are n processors in total core), where Cp (p∈N) represents the attribute of the pth processor core, Indicates the communication attributes between any two task nodes i and j with dependencies between the two processor cores p and q.
每个任务节点i的属性如式(1)所示：The attributes of each task node i are shown in formula (1):
Ii＝<F,Ti,p,Pi,p>(i∈M,p∈N) (1)Ii =<F,Ti,p ,Pi,p >(i∈M,p∈N) (1)
其中，F表示第i个任务节点的识别号，Ti,p表示第i个任务节点在第p个处理器核上的任务执行时间损失，Pi,p表示第i个任务节点在第p个处理器核上的任务执行功率消耗。Among them, F represents the identification number of the i-th task node, Ti,p represents the task execution time loss of the i-th task node on the p-th processor core, Pi,p represents the i-th task node at p Task execution power consumption on each processor core.
系统中任意有依赖关系的i,j两个任务节点在第p,q两个处理器核间通信属性如式(2)所示：The communication attributes between the two processor cores p and q of any dependent i and j task nodes in the system are shown in formula (2):
其中，表示任意有依赖关系的i,j两个任务节点在第p,q两个处理器核间通信时间消耗，表示任意有依赖关系的i,j两个任务节点在第p,q两个处理器核间通信功率消耗。in, Indicates the communication time consumption between any two task nodes i and j with dependencies between the two processor cores p and q, Indicates the communication power consumption between the two processor cores p and q of any dependent i and j task nodes.
基于异构多核模型的任务分配问题可以看作在执行功耗的约束下将所有任务节点的执行时间以及任意有依赖关系的两个任务节点的通信时间之和作为寻优目标，则其数学模型描述如式(3)所示：The task allocation problem based on the heterogeneous multi-core model can be regarded as the sum of the execution time of all task nodes and the communication time of any two task nodes with dependencies as the optimization goal under the constraint of execution power consumption, then its mathematical model The description is shown in formula (3):
min:min:
subject to:subject to:
针对基于异构多核模型的任务分配问题，可以将M个任务节点的任务分配方案对应一个M维的空间。其中每个人物节点的实现方案可以由0,1,2,...,p,...,N表示，即p表示当前任务节点由第p个处理器核执行。基于异构多核的任务分配问题可以理解为寻找最优的任务分配方案的过程。For the task allocation problem based on the heterogeneous multi-core model, the task allocation scheme of M task nodes can be corresponding to an M-dimensional space. The implementation scheme of each character node can be represented by 0, 1, 2, ..., p, ..., N, that is, p means that the current task node is executed by the pth processor core. The task allocation problem based on heterogeneous multi-core can be understood as the process of finding the optimal task allocation scheme.
2、传统的人工蜂群算法在异构多核任务分配问题上的应用2. Application of traditional artificial bee colony algorithm in heterogeneous multi-core task allocation problem
人工蜂群算法(Artificial Bee Colony Algorithm,ABCA)是一种新型群体智能优化算法，具备系统学中的整体性、关联性、动态性和有序性等特点，也体现了群体行为的分布式特点，具有能从无序到有序的进行自组织进化过程的特点。其思想来源于蜂群的觅食行为。蜂群在觅食、繁衍后代等行为中个体与群体间、群体与群体间互相合作、相互协调，通过舞蹈和气味等信息进行信息交流和共享。在这些文化信息的交流的基础上进行觅食。在觅食的过程中，蜂群将蜂分为雇佣蜂、侦察蜂和跟随蜂，它们都有各自的分工，侦察蜂负责对食物源的侦查，跟随蜂和雇佣蜂负责对食物源进行开采。蜂群保持着很好的协调作用，能够达到较好的平衡，进而完成蜂群群体的觅食、繁衍等行为。算法应用于异构多核任务分配时要先根据种群规模随机获得相同数量的可行解，然后进入迭代过程，初始时刻将蜂群平均分为雇佣蜂和跟随蜂，雇佣蜂先进行食物源的寻找，记录寻找到的食物源及其相应的适应度函数值，对寻找到的食物源进行邻域搜索，并纪录邻域食物源的相应适应度函数，如果邻域食物源相应的解的质量好于当前食物源相应的解的质量，则将当前位置的食物源替换为邻域位置的食物源。然后根据每个食物源相应解的质量派遣跟随蜂执行邻域搜索，解得的质量越高，食物源的收益度越大，执行邻域搜索的可能性越大，进行邻域搜索时若邻域食物源的相应解得质量好于当前位置的解的质量，则用领域食物源替换当前位置的食物源。如果某个位置的食物源进行多次迭代相应的解的质量仍不能得到提高，则这个位置的食物源将被抛弃，拥有当前食物源的雇佣蜂将变为侦察蜂重新寻找新的食物源，之后再对新的食物源进行邻域搜索。按照这种方式进行反复循环迭代，直到完成输出符合条件的最优解作为当前任务分配的最佳方案。Artificial Bee Colony Algorithm (ABCA) is a new type of swarm intelligence optimization algorithm, which has the characteristics of integrity, relevance, dynamics and order in systematics, and also reflects the distributed characteristics of group behavior. , has the characteristic of self-organized evolution process from disorder to order. The idea comes from the foraging behavior of bee colonies. The bee colony cooperates and coordinates with each other and coordinates between individuals and groups, and between groups in the behaviors of foraging and reproduction, and exchanges and shares information through information such as dance and smell. Foraging is based on the exchange of these cultural messages. In the process of foraging, the bee colony divides bees into hired bees, scout bees and follower bees. They all have their own division of labor. The scout bees are responsible for the detection of food sources, and the follower bees and hired bees are responsible for mining food sources. The bee colony maintains a good coordination function, can achieve a better balance, and then completes the behaviors such as foraging and reproduction of the bee colony. When the algorithm is applied to the allocation of heterogeneous multi-core tasks, the same number of feasible solutions should be randomly obtained according to the population size, and then enter the iterative process. At the initial moment, the bee colony is divided into hired bees and follower bees on average. Record the found food source and its corresponding fitness function value, perform a neighborhood search on the found food source, and record the corresponding fitness function of the neighborhood food source, if the quality of the corresponding solution of the neighborhood food source is better than The quality of the solution corresponding to the current food source, replace the food source at the current position with the food source at the neighboring position. Then according to the quality of the corresponding solution of each food source, follower bees are dispatched to perform neighborhood search. The higher the quality of the solution, the greater the profitability of the food source, and the greater the possibility of performing neighborhood search. If the quality of the corresponding solution of the domain food source is better than the quality of the solution at the current position, replace the food source at the current position with the domain food source. If the quality of the corresponding solution of the food source at a certain position cannot be improved after multiple iterations, the food source at this position will be discarded, and the hired bee with the current food source will become a scout bee to search for a new food source again. Afterwards, a neighborhood search is performed for new food sources. In this way, repeated loop iterations are performed until the optimal solution that meets the conditions is output as the best solution for the current task assignment.
发明内容Contents of the invention
本发明所要解决的技术问题是，提供一种比原始蜂群算法性能更好的基于改进蜂群算法的异构多核任务分配方法。The technical problem to be solved by the present invention is to provide a heterogeneous multi-core task allocation method based on the improved bee colony algorithm with better performance than the original bee colony algorithm.
本发明所采用的技术方案是：一种基于改进蜂群算法的异构多核任务分配方法，包括如下步骤：The technical solution adopted in the present invention is: a method for distributing heterogeneous multi-core tasks based on the improved bee colony algorithm, comprising the following steps:
1)初始化参数，包括：雇佣蜂的种群规模Q，跟随蜂的种群规模W，确定异构多核模型的功耗约束参数，确定算法的最大迭代次数IterMax，以及算法的终止条件为当迭代次数到达最大迭代次数时停止算法的迭代，设定第一限定阈值H为更改某一食物源搜索策略的食物源迭代次数阈值，设定第二限定阈值iter_Limit为抛弃某一食物源的食物源迭代次数阈值，设定第三限定阈值iter_change为改变侦查蜂对食物源重新生产方式的算法迭代次数阈值；1) Initialization parameters, including: the population size Q of employed bees, the population size W of follower bees, determining the power consumption constraint parameters of the heterogeneous multi-core model, determining the maximum number of iterations IterMax of the algorithm, and the termination condition of the algorithm is when the number of iterations reaches Stop the iteration of the algorithm when the maximum number of iterations is reached, set the first limit threshold H as the food source iteration threshold for changing a certain food source search strategy, and set the second limit threshold iter_Limit as the food source iteration threshold for discarding a certain food source , set the third limited threshold iter_change as the algorithm iteration threshold for changing the way scout bees reproduce food sources;
2)初始化食物源规模，包括对于M个任务节点组成的任务集，首先生成与雇佣蜂的种群规模Q个数相同的符合处理器核功率约束的食物源坐标，每个食物源为M位的0～(N-1)的随机编码序列；2) Initialize the food source scale, including for a task set composed of M task nodes, first generate the same food source coordinates as the population size Q of hired bees that meet the processor core power constraints, and each food source is M-bit 0～(N-1) random coding sequence;
3)迭代更新开始，计算每个食物源的适应度函数值，适应度函数值最大的食物源为当前最优食物源；3) The iterative update starts, and the fitness function value of each food source is calculated, and the food source with the largest fitness function value is the current optimal food source;
4)对算法的迭代次数Iter加1，判断迭代次数Iter是否大于设定的最大迭代次数IterMax，是执行步骤16)，否则执行步骤5)。4) Add 1 to the iteration number Iter of the algorithm, and judge whether the iteration number Iter is greater than the set maximum iteration number IterMax, and execute step 16), otherwise execute step 5).
5)跟随蜂进行邻域搜索，具体是对当前食物源所对应的编码信息的一比特值进行更新实现的，并分别计算当前食物源与邻域食物源对应的解的质量；5) Follow the bee to perform neighborhood search, specifically by updating the one-bit value of the coded information corresponding to the current food source, and calculate the quality of the solutions corresponding to the current food source and the neighborhood food source;
6)如果邻域食物源对应的解的质量大于当前食物源对应的解的质量则执行步骤7)，否则执行步骤8)；6) If the quality of the solution corresponding to the neighborhood food source is greater than the quality of the solution corresponding to the current food source, then perform step 7), otherwise perform step 8);
7)用邻域食物源替换当前食物源，并返回步骤4)；7) replace the current food source with the neighborhood food source, and return to step 4);
8)对当前食物源的迭代次数加1，判断迭代次数是否大于第一限定阈值H，如果大于限定的阈值H则执行步骤9)，否则返回步骤5)；8) Add 1 to the number of iterations of the current food source, determine whether the number of iterations is greater than the first defined threshold H, if greater than the defined threshold H, then perform step 9), otherwise return to step 5);
9)进行改进的邻域搜索，寻找邻域内更优的食物源，具体是对当前食物源所对应的编码信息改变设定比特数的编码信息，并计算当前食物源与邻域食物源对应的解的质量；9) Carry out an improved neighborhood search to find a better food source in the neighborhood. Specifically, change the coding information of the set number of bits for the coding information corresponding to the current food source, and calculate the corresponding ratio between the current food source and the neighborhood food source. the quality of the solution;
10)如果邻域食物源对应解的质量大于当前食物源对应解的质量，则执行步骤11)，否则执行步骤12)；10) If the quality of the solution corresponding to the neighborhood food source is greater than the quality of the solution corresponding to the current food source, then perform step 11), otherwise perform step 12);
11)用邻域食物源替换当前食物源，并返回步骤4)；11) replace the current food source with the neighborhood food source, and return to step 4);
12)对当前食物源的迭代次数加1，判断当前食物源迭代次数是否大于第二限定阈值iter_Limit，如果是则执行步骤13)，否则返回步骤9)；12) Add 1 to the number of iterations of the current food source, and judge whether the number of iterations of the current food source is greater than the second limit threshold iter_Limit, if so, execute step 13), otherwise return to step 9);
13)判断算法的迭代次数Iter否大于第三限定阈值iter_change，如果是则执行步骤14)，否则执行步骤15)；13) Whether the iterative times Iter of judging algorithm is greater than the third limit threshold iter_change, if yes then execute step 14), otherwise execute step 15);
14)拥有当前食物的雇佣蜂变为侦查蜂，侦察蜂根据当前最优食物源的设定比特数的编码信息，重新生成新的食物源之后，侦查蜂再变回雇佣蜂，并返回步骤4)；14) The hired bee with the current food becomes a scout bee, and the scout bee regenerates a new food source according to the coded information of the set bit number of the current optimal food source, and then the scout bee turns back to a hired bee, and returns to step 4 );
15)拥有当前食物的雇佣蜂变为侦查蜂，侦察蜂初始化当前食物源之后，侦查蜂再变回雇佣蜂，并返回步骤4)；15) The hired bee with the current food becomes a scout bee. After the scout bee initializes the current food source, the scout bee changes back to the hired bee and returns to step 4);
16)输出当前最优食物源的位置坐标即为最佳的任务分配方案。16) Outputting the position coordinates of the current optimal food source is the optimal task allocation scheme.
步骤3)所述的计算每个食物源的适应度函数值，是Step 3) described in calculating the fitness function value of each food source, is
TS和PowerS分别为第S个食物源即第S个任务分配方案所需要的时间损耗之和与功率损失之和；TS and PowerS are respectively the sum of time loss and power loss required by the Sth food source, that is, the Sth task allocation plan;
设定共有N个处理器核，每个食物源即每个任务分配方案共有M个任务节点，i,j∈M，p,q∈N，Ti,p表示第i个任务节点在第p个处理器核上的任务执行时间损失，Pi,p表示第i个任务节点在第p个处理器核上的任务执行功率消耗。表示任意有依赖关系的i,j两个任务节点在第p,q两个处理器核间通信时间消耗，表示任意有依赖关系的i,j两个任务节点在第p,q两个处理器核间通信功率消耗；TimeLimit和PowerLimit分别为设定的时间约束和功率约束。It is assumed that there are a total of N processor cores, each food source, that is, each task allocation scheme has a total of M task nodes, i,j∈M, p,q∈N, Ti,p means that the i-th task node is at p The task execution time loss on a processor core, Pi,p represents the task execution power consumption of the i-th task node on the p-th processor core. Indicates the communication time consumption between any two task nodes i and j with dependencies between the two processor cores p and q, Indicates the communication power consumption between the two processor cores p and q of any dependent i and j task nodes; TimeLimit and PowerLimit are the set time constraints and power constraints respectively.
步骤5)和步骤9)所述的计算当前食物源与邻域食物源对应的解的质量即为由适应度函数计算所得值，计算适应度函数所得值越大得到的解的质量越好。The quality of the solution corresponding to the current food source and the neighborhood food source in steps 5) and 9) is the value calculated by the fitness function, and the larger the value obtained by the fitness function, the better the quality of the solution.
本发明的一种基于改进蜂群算法的异构多核任务分配方法，在寻优的后期，当对当前食物源进行邻域搜索不能提高解的质量的时候，侦察蜂重新生成食物源时参考当前最优食物源的信息编码，根据当前最优食物源的信息重新生成新的食物源，在此基础上再进行邻域搜索。这样会大大减少无效的迭代次数，在一定程度上提高蜂群算法的收敛速度，提高任务分配效率。A heterogeneous multi-core task assignment method based on the improved bee colony algorithm of the present invention, in the later stage of optimization, when the neighborhood search for the current food source cannot improve the quality of the solution, the scout bees refer to the current food source when regenerating the food source The information encoding of the optimal food source is used to regenerate a new food source based on the information of the current optimal food source, and then the neighborhood search is performed on this basis. This will greatly reduce the number of invalid iterations, improve the convergence speed of the bee colony algorithm to a certain extent, and improve the efficiency of task allocation.
附图说明Description of drawings
图1是现有技术的邻域搜索策略示意图；FIG. 1 is a schematic diagram of a neighborhood search strategy in the prior art;
图2是本发明的邻域搜索策略示意图；Fig. 2 is a schematic diagram of the neighborhood search strategy of the present invention;
图3是本发明的侦察蜂重新生成食物源示意图。Fig. 3 is a schematic diagram of scout bees regenerating food sources of the present invention.
具体实施方式Detailed ways
下面结合实施例和附图对本发明的一种基于改进蜂群算法的异构多核任务分配方法做出详细说明。A method for allocating heterogeneous multi-core tasks based on the improved bee colony algorithm of the present invention will be described in detail below in conjunction with the embodiments and the accompanying drawings.
本发明的一种基于改进蜂群算法的异构多核任务分配方法，主要对原始算法进行两点改进A heterogeneous multi-core task allocation method based on the improved bee colony algorithm of the present invention mainly improves the original algorithm by two points
1、邻域搜索方式的改进1. Improvement of neighborhood search method
原始蜂群算法每一次对食物源的邻域搜索方式是通过对该事务员对应编码信息的一比特进行更新实现的，当初始食物源的位置非常接近最近最优食物源时，对应的编码信息差异较小，通过改变一比特就能够较快的寻找到最优解，但如果当前食物源和最优食物源的位置差别很大，即当前食物源的解的质量较差时，如果每次更新的位数仍为一位时，显然其收敛速度会降低，会增加无效迭代次数，降低任务分配效率。The original bee colony algorithm searches the neighborhood of the food source each time by updating one bit of the corresponding coding information of the clerk. When the initial food source is very close to the nearest optimal food source, the corresponding coding information The difference is small, and the optimal solution can be found quickly by changing one bit, but if the position of the current food source and the optimal food source are very different, that is, the quality of the solution of the current food source is poor, if each When the updated number of digits is still one, obviously its convergence speed will be reduced, the number of invalid iterations will be increased, and the efficiency of task allocation will be reduced.
本发明中针对原始蜂群算法收敛速度慢，搜索能力差对邻域搜索方式进行了改进。首先对邻域搜索次数设置一个搜索次数阈值H，当搜索次数低于阈值H时，领域搜索策略为更新一位实现迭代更新，并对邻域食物源进行相应的解的计算，当搜索次数高于阈值H时，领域搜索策略为更新多位实现迭代更新，并对邻域食物源进行相应的解的计算，从而快速的实现解的收敛。In the present invention, the neighborhood search mode is improved for the original bee colony algorithm with slow convergence speed and poor search ability. First, set a search times threshold H for the number of neighborhood searches. When the number of searches is lower than the threshold H, the domain search strategy is to update one bit to achieve iterative update, and calculate the corresponding solution for the neighborhood food source. When the number of searches is high At the threshold H, the domain search strategy is to update multiple bits to implement iterative update, and calculate the corresponding solution for the neighborhood food source, so as to quickly achieve the convergence of the solution.
2、侦察蜂生成新的食物源的生成方式2. How scout bees generate new food sources
原始蜂群算法中如果一个食物源邻域搜索次数大于该食物源的最大限制更新次数iter_Limit仍不能提高该食物源相应解的质量，那么侦察蜂将对该食物源进行初始化。在蜂群算法寻优的后期，原始蜂群算法重新生成食物源的方式增加了冗余的更新食物源的过程，大大降低蜂群算法的收敛速度。In the original bee colony algorithm, if the number of neighborhood searches of a food source is greater than the maximum limit update times iter_Limit of the food source and the quality of the corresponding solution of the food source cannot be improved, then the scout bee will initialize the food source. In the later stage of the optimization of the bee colony algorithm, the way of regenerating the food source by the original bee colony algorithm increases the process of updating the food source redundantly, which greatly reduces the convergence speed of the bee colony algorithm.
本发明的一种基于改进蜂群算法的异构多核任务分配方法，包括如下步骤：A kind of heterogeneous multi-core task allocation method based on improved bee colony algorithm of the present invention comprises the following steps:
1)初始化参数，包括：雇佣蜂的种群规模Q，跟随蜂的种群规模W，确定异构多核模型的功耗约束(PowerLimit)参数，确定算法的最大迭代次数IterMax，以及算法的终止条件为当迭代次数到达最大迭代次数时停止算法的迭代，设定第一限定阈值H为更改某一食物源搜索策略的食物源迭代次数阈值，设定第二限定阈值iter_Limit为抛弃某一食物源的食物源迭代次数阈值，设定第三限定阈值iter_change为改变侦查蜂对食物源重新生产方式的算法迭代次数阈值。；1) Initialization parameters, including: the population size Q of hired bees, the population size W of follower bees, the determination of the power consumption constraint (PowerLimit) parameter of the heterogeneous multi-core model, the determination of the maximum number of iterations IterMax of the algorithm, and the termination condition of the algorithm when Stop the iteration of the algorithm when the number of iterations reaches the maximum number of iterations, set the first limit threshold H as the food source iteration threshold for changing a certain food source search strategy, and set the second limit threshold iter_Limit as the food source for discarding a certain food source Iteration threshold, set the third threshold iter_change as the algorithm iteration threshold for changing the way scout bees reproduce food sources. ;
2)初始化食物源规模，包括对于M个任务节点组成的任务集，首先生成与雇佣蜂的种群规模Q个数相同的符合处理器核功率约束的食物源坐标，每个食物源为M位的0～N-1的随机编码序列；2) Initialize the food source scale, including for a task set composed of M task nodes, first generate the same food source coordinates as the population size Q of hired bees that meet the processor core power constraints, and each food source is M-bit Random coding sequence from 0 to N-1;
3)迭代更新开始，计算每个食物源的适应度函数值，适应度函数值最大的食物源为当前最优食物源；3) The iterative update starts, and the fitness function value of each food source is calculated, and the food source with the largest fitness function value is the current optimal food source;
TS和PowerS分别为第S个食物源即第S个任务分配方案所需要的时间损耗之和与功率损失之和。TS and PowerS are respectively the sum of time loss and power loss required by the Sth food source, that is, the Sth task allocation scheme.
设定共有N个处理器核，每个食物源即每个任务分配方案共有M个任务节点，i,j∈M，p,q∈N，Ti,p表示第i个任务节点在第p个处理器核上的任务执行时间损失，Pi,p表示第i个任务节点在第p个处理器核上的任务执行功率消耗。表示任意有依赖关系的i,j两个任务节点在第p,q两个处理器核间通信时间消耗，表示任意有依赖关系的i,j两个任务节点在第p,q两个处理器核间通信功率消耗。TimeLimit和PowerLimit分别为设定的时间约束和功率约束。It is assumed that there are a total of N processor cores, each food source, that is, each task allocation scheme has a total of M task nodes, i,j∈M, p,q∈N, Ti,p means that the i-th task node is at p The task execution time loss on a processor core, Pi,p represents the task execution power consumption of the i-th task node on the p-th processor core. Indicates the communication time consumption between any two task nodes i and j with dependencies between the two processor cores p and q, Indicates the communication power consumption between the two processor cores p and q of any dependent i and j task nodes. TimeLimit and PowerLimit are the set time constraints and power constraints respectively.
4)对算法的迭代次数Iter加1，判断迭代次数Iter是否大于设定的最大迭代次数IterMax，是执行步骤16)，否则执行步骤5)，4) Add 1 to the number of iterations Iter of the algorithm, judge whether the number of iterations Iter is greater than the maximum number of iterations IterMax of setting, is to execute step 16), otherwise execute step 5),
5)跟随蜂进行邻域搜索，具体是对当前食物源所对应的编码信息的一比特值进行更新实现的，并分别计算当前食物源与邻域食物源对应的解的质量；所述的计算当前食物源与邻域食物源对应的解的质量，即计算当前食物源与邻域食物源对应的解的质量即为由适应度函数计算所得值，计算适应度函数所得值越大得到的解的质量越好；5) Follow the bees to search the neighborhood, specifically, update the one-bit value of the coded information corresponding to the current food source, and calculate the quality of the solutions corresponding to the current food source and the neighborhood food source; The quality of the solution corresponding to the current food source and the neighborhood food source, that is, the quality of the solution corresponding to the current food source and the neighborhood food source is the value calculated by the fitness function, and the larger the value obtained by calculating the fitness function, the solution the better the quality;
6)如果邻域食物源对应的解的质量大于当前食物源对应的解的质量则执行步骤7)，否则执行步骤8)；6) If the quality of the solution corresponding to the neighborhood food source is greater than the quality of the solution corresponding to the current food source, then perform step 7), otherwise perform step 8);
7)用邻域食物源替换当前食物源，并返回步骤4)；7) replace the current food source with the neighborhood food source, and return to step 4);
8)对当前食物源的迭代次数加1，判断迭代次数是否大于第一限定阈值H，如果大于限定的阈值H则执行步骤9)，否则返回步骤5)；8) Add 1 to the number of iterations of the current food source, determine whether the number of iterations is greater than the first defined threshold H, if greater than the defined threshold H, then perform step 9), otherwise return to step 5);
9)进行改进的邻域搜索，寻找邻域内更优的食物源，具体是对当前食物源所对应的编码信息改变设定比特数的编码信息，并计算当前食物源与邻域食物源对应的解的质量；所述的计算当前食物源与邻域食物源对应的解的质量，是采用与步骤5)相同的方式进行计算。9) Carry out an improved neighborhood search to find a better food source in the neighborhood. Specifically, change the coding information of the set number of bits for the coding information corresponding to the current food source, and calculate the corresponding ratio between the current food source and the neighborhood food source. The quality of the solution; the calculation of the quality of the solution corresponding to the current food source and the neighborhood food source is performed in the same manner as step 5).
10)如果邻域食物源对应解的质量大于当前食物源对应解的质量，则执行步骤11)，否则执行步骤12)；10) If the quality of the solution corresponding to the neighborhood food source is greater than the quality of the solution corresponding to the current food source, then perform step 11), otherwise perform step 12);
11)用邻域食物源替换当前食物源，并返回步骤4)；11) replace the current food source with the neighborhood food source, and return to step 4);
12)对当前食物源的迭代次数加1，判断当前食物源迭代次数是否大于第二限定阈值iter_Limit，如果是则执行步骤12)，否则返回步骤8)；12) Add 1 to the number of iterations of the current food source, and judge whether the number of iterations of the current food source is greater than the second limit threshold iter_Limit, if so, execute step 12), otherwise return to step 8);
13)判断算法的迭代次数Iter是否大于第三限定阈值iter_change，如果是则执行步骤13)，否则执行步骤14)；13) judge whether the number of iterations Iter of the algorithm is greater than the third limit threshold iter_change, if yes then perform step 13), otherwise perform step 14);
14)拥有当前食物的雇佣蜂变为侦查蜂，侦察蜂根据当前最优食物源的设定比特数的编码信息，重新生成新的食物源之后，侦查蜂再变回雇佣蜂，之后侦查蜂再变回雇佣蜂，并返回步骤4)；14) The hired bees with the current food become scout bees, and the scout bees regenerate a new food source according to the coded information of the set bit number of the current optimal food source, and then the scout bees turn back into hired bees, and then the scout bees regenerate a new food source. Change back to employed bees, and return to step 4);
15)拥有当前食物的雇佣蜂变为侦查蜂，侦察蜂初始化当前食物源之后，侦查蜂再变回雇佣蜂，并返回步骤4)；如图3所示。15) The hired bee with the current food becomes a scout bee. After the scout bee initializes the current food source, the scout bee changes back to the hired bee and returns to step 4); as shown in Figure 3.
16)输出当前最优食物源的位置坐标即为最佳的任务分配方案。16) Outputting the position coordinates of the current optimal food source is the optimal task allocation scheme.
邻域搜索策略的改进前、后如图1、图2所示，原始蜂群算法中跟随蜂进行邻域搜索时，对当前食物源的编码信息改变一比特进行邻域搜索，即改变图1中第M-3个任务的编码信息，由对应的处理器核0改为对应的处理器核2。本发明的方法中，侦察蜂在多次改变一比特位信息仍不能有效更新食物源时，则对当前食物源的编码信息改变多位进行邻域搜索，如图2所示，分别改变了第1、2、M-3和M-1个任务的编码信息。As shown in Figure 1 and Figure 2 before and after the improvement of the neighborhood search strategy, in the original bee colony algorithm, when following the bees to search the neighborhood, the coding information of the current food source is changed by one bit to perform the neighborhood search, that is, the change in Figure 1 The encoding information of the M-3th task in is changed from the corresponding processor core 0 to the corresponding processor core 2. In the method of the present invention, when the scout bees cannot effectively update the food source after changing one bit of information multiple times, they change multiple bits of the coding information of the current food source to perform a neighborhood search, as shown in Figure 2, respectively changing the first Coding information for 1, 2, M-3 and M-1 tasks.
针对30到132节点的不同规模的任务集，在减少100次迭代的前提下一种基于改进蜂群算法的异构多核任务分配方法较原始算法在求解质量上的提升程度如表1所示。For task sets of different scales from 30 to 132 nodes, under the premise of reducing 100 iterations, a heterogeneous multi-core task allocation method based on the improved bee colony algorithm improves the solution quality compared with the original algorithm, as shown in Table 1.
表1监督混洗蛙跳算法与原始混洗蛙跳算法性能对比Table 1 Performance comparison between the supervised shuffle leapfrog algorithm and the original shuffle leapfrog algorithm
下面给出最佳实例：Best examples are given below:
实例的具体参数设置如下：The specific parameters of the instance are set as follows:
1)初始化参数，雇佣蜂种群规模7只，跟随蜂种群规模7只，确定异构多核模型的功耗约束包括(PowerLimit)等参数，确定算法的最大迭代次数1000，以及算法的终止条件，设置模型为两个核。1) Initialize parameters, hire bee population size 7, follow bee population size 7, determine the power consumption constraints of the heterogeneous multi-core model including (PowerLimit) and other parameters, determine the maximum number of iterations of the algorithm 1000, and the termination condition of the algorithm, set The model is two cores.
2)初始化食物源规模；包括对于15个任务节点组成的任务集，首先生成7个符合处理器核功率约束的食物源坐标，每个位置坐标为0、1组成的M维向量，每个食物源15位的0～1随机编码序列。2) Initialize the food source scale; including for a task set composed of 15 task nodes, first generate 7 food source coordinates that meet the processor core power constraints, and each position coordinate is an M-dimensional vector composed of 0 and 1, and each food Source 15-bit 0-1 random coding sequence.
3)迭代更新开始，雇佣蜂初始化食物源，并计算每个食物源的适应度函数值，适应度函数值越小说明当前食物源越优，食物源对应的解越理想。3) The iterative update starts, the hired bee initializes the food source, and calculates the fitness function value of each food source. The smaller the fitness function value is, the better the current food source is, and the solution corresponding to the food source is more ideal.
4)跟随蜂进行邻域搜索，对算法的迭代次数Iter加1，判断Iter是否大于算法的最大迭代次数1000，如果否则对当前食物源对应的信息编码改变一比特值，并分别计算当前食物源与邻域食物源对应的解的质量，否则执行步骤15)。4) Follow the bees to search the neighborhood, add 1 to the iteration number Iter of the algorithm, and judge whether Iter is greater than the maximum number of iterations of the algorithm 1000, if not, change the information code corresponding to the current food source by one bit, and calculate the current food source respectively The quality of the solution corresponding to the neighborhood food source, otherwise go to step 15).
5)如果邻域食物源对应的解的质量好于当前食物源对应的解的质量则执行步骤6)，否则执行步骤7)。5) If the quality of the solution corresponding to the neighborhood food source is better than the quality of the solution corresponding to the current food source, perform step 6), otherwise perform step 7).
6)将当前食物源的替换为邻域食物源，并执行步骤4)。6) Replace the current food source with a neighboring food source, and perform step 4).
7)对该食物源的迭代次数加1，判断迭代次数是否大于限定的阈值10，如果大于限定的阈值10则执行步骤8)，否则返回步骤4)。7) Add 1 to the number of iterations of the food source, and judge whether the number of iterations is greater than the defined threshold 10, and if it is greater than the defined threshold 10, execute step 8), otherwise return to step 4).
8)对当前食物源对应的信息编码改变8位比特信息进行邻域搜索，快速的寻找邻域内更优的食物源，并计算当前食物源与邻域食物源对应的解的质量。8) Change the 8-bit information of the information code corresponding to the current food source to search the neighborhood, quickly find a better food source in the neighborhood, and calculate the quality of the solution corresponding to the current food source and the neighborhood food source.
9)对该食物源的相应迭代次数加1，如果邻域食物源好于当前食物源则执行步骤10)，否则执行步骤11)。9) Add 1 to the corresponding number of iterations of the food source, if the food source in the neighborhood is better than the current food source, then execute step 10), otherwise, execute step 11).
10)将当前食物源替换为邻域食物源，并执行步骤4)。10) Replace the current food source with a neighboring food source, and perform step 4).
11)判断当前食物源迭代次数是否大于限定阈值50次，如果是则执行步骤12)，否则返回步骤8)。11) Judging whether the iteration number of the current food source is greater than the defined threshold of 50 times, if yes, execute step 12), otherwise return to step 8).
12)判断算法的迭代次数Iter是否大于限定的阈值750次,如果是则执行步骤13)，否则执行步骤14)。12) Judging whether the number of iterations Iter of the algorithm is greater than the defined threshold 750 times, if so, perform step 13), otherwise perform step 14).
13)侦察蜂随机取8位最优食物源的编码信息，重新生成新的食物源，并返回步骤4)。13) The scout bee randomly picks the coded information of 8 optimal food sources, regenerates a new food source, and returns to step 4).
14)侦察蜂初始化当前食物源，并返回步骤3)。14) The scout bee initializes the current food source, and returns to step 3).
15)输出当前最优食物源的位置坐标即为最佳的任务分配方案。15) Outputting the position coordinates of the current optimal food source is the optimal task allocation scheme.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810160405.XACN108415783B (en) | 2018-02-27 | 2018-02-27 | Heterogeneous multi-core task allocation method based on improved bee colony algorithm |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810160405.XACN108415783B (en) | 2018-02-27 | 2018-02-27 | Heterogeneous multi-core task allocation method based on improved bee colony algorithm |
| Publication Number | Publication Date |
|---|---|
| CN108415783Atrue CN108415783A (en) | 2018-08-17 |
| CN108415783B CN108415783B (en) | 2021-12-07 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201810160405.XAActiveCN108415783B (en) | 2018-02-27 | 2018-02-27 | Heterogeneous multi-core task allocation method based on improved bee colony algorithm |
| Country | Link |
|---|---|
| CN (1) | CN108415783B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109886574A (en)* | 2019-02-20 | 2019-06-14 | 哈尔滨工程大学 | A multi-robot task assignment method based on improved threshold method |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20130051632A1 (en)* | 2011-08-25 | 2013-02-28 | King Saud University | Passive continuous authentication method |
| CN102982008A (en)* | 2012-11-01 | 2013-03-20 | 山东大学 | Complicated function maximum and minimum solving method by means of parallel artificial bee colony algorithm based on computer cluster |
| CN103116693A (en)* | 2013-01-14 | 2013-05-22 | 天津大学 | Hardware and software partitioning method based on artificial bee colony |
| CN104239269A (en)* | 2013-06-19 | 2014-12-24 | 苏州吉浦迅科技有限公司 | Computer cluster based intelligent parallel bee colony algorithm data system |
| US20150293582A1 (en)* | 2014-04-15 | 2015-10-15 | Pierre Popovic | Energy Efficient Blade Server and Method for Reducing the Power Consumption of a Data Center Using the Energy Efficient Blade Server |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20130051632A1 (en)* | 2011-08-25 | 2013-02-28 | King Saud University | Passive continuous authentication method |
| CN102982008A (en)* | 2012-11-01 | 2013-03-20 | 山东大学 | Complicated function maximum and minimum solving method by means of parallel artificial bee colony algorithm based on computer cluster |
| CN103116693A (en)* | 2013-01-14 | 2013-05-22 | 天津大学 | Hardware and software partitioning method based on artificial bee colony |
| CN104239269A (en)* | 2013-06-19 | 2014-12-24 | 苏州吉浦迅科技有限公司 | Computer cluster based intelligent parallel bee colony algorithm data system |
| US20150293582A1 (en)* | 2014-04-15 | 2015-10-15 | Pierre Popovic | Energy Efficient Blade Server and Method for Reducing the Power Consumption of a Data Center Using the Energy Efficient Blade Server |
| Title |
|---|
| XINXU ZHOU等: "Enhacing the modified artificial bee colony algorithm with neighborhood search", 《SOFT COMPUTING》* |
| 火久元等: ""一种劣解突变策略引导的混合人工蜂群算法"", 《计算机应用与软件》* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109886574A (en)* | 2019-02-20 | 2019-06-14 | 哈尔滨工程大学 | A multi-robot task assignment method based on improved threshold method |
| CN109886574B (en)* | 2019-02-20 | 2023-02-14 | 哈尔滨工程大学 | Multi-robot task allocation method based on improved threshold method |
| Publication number | Publication date |
|---|---|
| CN108415783B (en) | 2021-12-07 |
| Publication | Publication Date | Title |
|---|---|---|
| CN105550033B (en) | Resource dispatching strategy method based on genetic tabu hybrid algorithm under privately owned cloud environment | |
| CN102843743B (en) | To look for food based on flora the wireless sense network Tiered routing method of optimized algorithm | |
| CN113098714A (en) | Low-delay network slicing method based on deep reinforcement learning | |
| CN114710439B (en) | Network energy consumption and throughput joint optimization routing method based on deep reinforcement learning | |
| CN109656713B (en) | Container scheduling method based on edge computing framework | |
| CN112436992A (en) | Virtual network mapping method and device based on graph convolution network | |
| CN115329985A (en) | Unmanned cluster intelligent model training method and device and electronic equipment | |
| CN119311414B (en) | Heterogeneous GPU load balancing-based graph neural network partitioning method | |
| CN116363449A (en) | An Image Recognition Method Based on Hierarchical Federated Learning | |
| CN109636709B (en) | A Graph Computing Method for Heterogeneous Platforms | |
| CN117170836A (en) | Video cloud transcoding task scheduling method and device based on improved HHO algorithm | |
| CN111460275B (en) | Social network-oriented dynamic network representation learning method and system | |
| CN108415783B (en) | Heterogeneous multi-core task allocation method based on improved bee colony algorithm | |
| CN113572647B (en) | A blockchain-edge computing joint system based on reinforcement learning | |
| CN118070926B (en) | Multi-task federation learning method based on client resource self-adaption | |
| CN119313115A (en) | A resource pool scheduling strategy optimization method based on improved blockchain | |
| CN119521309A (en) | Task scheduling method based on improved bat algorithm in mobile edge computing environment | |
| CN118132268A (en) | Adaptive scheduling method for cloud resources based on learning exponential distribution optimization algorithm | |
| CN118647075A (en) | A wireless ad hoc network power control method, medium and electronic device | |
| CN111782398B (en) | Data processing method, device, system and related equipment | |
| CN108415773A (en) | A kind of efficient Method for HW/SW partitioning based on blending algorithm | |
| CN117195001A (en) | HPC job power consumption prediction method and system based on power consumption curve and script information | |
| WO2022186808A1 (en) | Method for solving virtual network embedding problem in 5g and beyond networks with deep information maximization using multiple physical network structure | |
| CN116542802A (en) | Method and System for Community Discovery Based on Graph Attention Autoencoder | |
| CN115904533A (en) | Edge calculation task unloading method based on deep reinforcement learning |
| 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 |