US2024411589A1PendingUtilityA1
Task scheduling method based on improved chimpanzee optimization algorithm
Assignee: UNIV NANJING POSTS & TELECOMMUNICATIONSPriority: Jun 7, 2023Filed: Oct 30, 2023Published: Dec 12, 2024
Est. expiryJun 7, 2043(~16.8 yrs left)· nominal 20-yr term from priority
G06F 9/4881
55
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
The present application discloses a task scheduling method based on an improved chimpanzee optimization algorithm, including obtaining a task to be scheduled and a task scheduling model pre-established by using a chimpanzee optimization algorithm, performing iterative computation of chimpanzees in the task scheduling model by the chimpanzee optimization algorithm; and ending the iterative computation in response to that an iteration termination condition is reached, outputting an optimal solution, and obtaining an optimal scheduling scheme. The present application solves the problem of the traditional chimpanzee optimization algorithm in the prior art that is prone to falling into the local optimum, and the imbalance between the global exploration capacity and the local exploitation capacity, the improved chimpanzee optimization algorithm has different aspects of performance enhancement compared to general intelligence algorithms of population.
Claims
exact text as granted — not AI-modified1 . A task scheduling method based on an improved chimpanzee optimization algorithm, comprising:
obtaining a task to be scheduled and a task scheduling model pre-established by using a chimpanzee optimization algorithm, and initializing a population and a parameter by using a two-dimensional function Halton sequence; performing iterative computation of chimpanzees in the task scheduling model by the chimpanzee optimization algorithm; and ending the iterative computation in response to that an iteration termination condition is reached, outputting an optimal solution, and obtaining an optimal scheduling scheme.
2 . The task scheduling method based on the improved chimpanzee optimization algorithm according to claim 1 , wherein the performing iterative computation of chimpanzees in the task scheduling model by the chimpanzee optimization algorithm comprises:
obtaining an initial population position and an initial adaptation of each chimpanzee in the population, sorting the population according to a value of the adaptation and dividing a role of the population, and obtaining an initial population role position; updating the population position and the population role position according to a sine-cosine optimization strategy to obtain an updated adaptation of each chimpanzee in the population; and wherein the task scheduling model pre-established by using the chimpanzee optimization algorithm comprises: taking a plurality of virtual machines in a cloud computing as a plurality of chimpanzees in the population, taking task assignment to the virtual machines as a process of the plurality of chimpanzees driving and chasing preys, and the process of the plurality of chimpanzees driving and chasing the preys being a process of finding the optimal solution.
3 . The task scheduling method based on the improved chimpanzee optimization algorithm according to claim 2 , wherein the two-dimensional function Halton sequence comprises:
n
=
∑
i
=
0
m
b
i
·
p
i
=
b
m
·
p
m
+
⋯
+
b
1
·
p
1
+
b
0
;
θ
(
n
)
=
b
0
·
p
-
1
+
b
1
·
p
-
2
+
⋯
+
b
m
·
p
-
m
-
1
;
H
(
n
)
=
[
θ
1
(
n
)
,
θ
2
(
n
)
]
;
wherein n is any integer within [1, N], N is a number of individuals in the population, p is a prime number not less than 2, b i ∈{0, 1, 2 . . . , p−1} is a constant, θ(n) is a defined sequence function, H(n) is a final obtained two-dimensional Halton sequence, m is a number of nodes, n is a total number of tasks, i is greater than and equal to 1 and less than and equal to N, and i is a number of cycles;
wherein a position of a Nth chimpanzee is X ij , i∈{1, 2, . . . , m}, j∈{1, 2, . . . , n}.
4 . The task scheduling method based on the improved chimpanzee optimization algorithm according to claim 3 , wherein the sorting the population according to the value of the adaptation and dividing the role of the population, and obtaining the initial population role position comprises:
sorting the population according to the value of the adaptation from high to low and dividing the role of the population, wherein the role of the population comprises an attacker, a barrier, a chaser and a driver; the attacker is a current optimal solution, and the other three are descending in order; obtaining a mathematical model of the process of the plurality of chimpanzees driving and chasing the preys according to the role of the population, the mathematical model being:
d
(
t
)
=
❘
"\[LeftBracketingBar]"
c
·
X
prey
(
t
)
-
h
·
X
chimp
(
t
)
❘
"\[RightBracketingBar]"
;
X
chimp
(
t
+
1
)
=
X
prey
(
t
)
-
a
·
d
;
wherein t is a current number of iterations, d is a distance of each chimpanzee from the prey, a and c are coefficient vectors, h is a chaotic mapping vector, h represents an effect of sexual motivation of the chimpanzee population during a hunting process, X prey is a vector of a position of the prey, X chimp is a vector of a position where the chimpanzee is currently located, d(t) is a vector of a distance of each chimpanzee from the prey under the current number of iterations, and X chimp (t+1) is a vector of a position where the chimpanzee is located under a next number of iterations.
5 . The task scheduling method based on the improved chimpanzee optimization algorithm according to claim 4 , wherein the obtaining the initial population role position comprises:
selecting four candidate solutions with a highest degree of adaptation according to the role of the population and the mathematical model of the process of the chimpanzee driving and chasing the preys, and obtaining the vector of positions of the other chimpanzees and a vector of the initial population role position by a position vector computation formula, the position vector computation formula comprising:
d
Attacker
=
❘
"\[LeftBracketingBar]"
c
1
·
X
Attacker
-
h
1
·
X
❘
"\[RightBracketingBar]"
;
d
Barrier
=
❘
"\[LeftBracketingBar]"
c
2
·
X
Barrier
-
h
2
·
X
❘
"\[RightBracketingBar]"
;
d
Chaser
=
❘
"\[LeftBracketingBar]"
c
3
·
X
Chaser
-
h
3
·
X
❘
"\[RightBracketingBar]"
;
d
Driver
=
❘
"\[LeftBracketingBar]"
c
4
·
X
Driver
-
h
4
·
X
❘
"\[RightBracketingBar]"
;
X
1
=
X
Attacker
-
a
1
·
d
Attacker
;
X
2
=
X
Barrier
-
a
2
·
d
Barrier
;
X
3
=
X
Chaser
-
a
3
·
d
Chaser
;
X
4
=
X
Driver
-
a
4
·
d
Driver
;
X
(
t
+
1
)
=
X
1
+
X
2
+
X
3
+
X
4
4
;
wherein d Attacker is a distance between the attacker chimpanzee and the prey, d Barrier is a distance between the barrier chimpanzee and the prey, d Chaser is a distance between the chaser chimpanzee and the prey, d Driver is a distance between the driver chimpanzee and the prey, X Attacker is a vector of position of the attacker chimpanzee, X Barrier is a vector of position of the barrier chimpanzee, X Chaser is a vector of position of the chaser chimpanzee, X Driver is a vector of position of the driver chimpanzee; c 1 c 2 c 3 c 4 , a 1 a 2 a 3 a 4 are all coefficient vectors, h 1 h 2 h 3 h 4 represent the effect of sexual motivation of the chimpanzee population during the hunting process, X 1 , X 2 , X 3 , X 4 are the vectors of the positions during calculation, X(t+1) is a vector of position at next moment, and X is a vector of position at current moment.
6 . The task scheduling method based on the improved chimpanzee optimization algorithm according to claim 5 , wherein the updating the population position and the population role position according to the sine-cosine optimization strategy comprises:
correcting a position update strategy of an original chimpanzee optimization algorithm according to the sine-cosine optimization strategy, calculating a position where the optimal solution locates while balancing the algorithm, and the corrected position update strategy is:
X
(
t
+
1
)
=
{
X
(
t
)
+
r
3
×
sin
(
2
π
r
4
)
×
D
θ
,
r
5
<
0.5
X
(
t
)
+
r
3
×
cos
(
2
π
r
4
)
×
D
θ
,
r
5
≥
0.5
;
D
θ
=
❘
r
6
X
i
α
(
t
)
-
❘
"\[LeftBracketingBar]"
X
i
(
t
)
❘
"\[RightBracketingBar]"
;
r
3
=
2
-
2
×
t
T
;
where r 3 is a number that is adaptively reduced with the number of iterations, r 4 , r 5 and r 6 are random numbers within [0,1], and X(t) is an updated vector of position of the chimpanzee, D θ is a sine-cosine optimization strategy formula.
7 . The task scheduling method based on the improved chimpanzee optimization algorithm according to claim 1 , wherein the ending the iterative computation in response to that the iteration termination condition is reached, outputting the optimal solution, and obtaining the optimal scheduling scheme, further comprising:
in response to that t is less than T, the iteration termination condition is reached, ending the iterative computation, outputting the optimal solution, and obtaining the optimal scheduling scheme; in response to that t is greater than and equal to T, the iteration termination condition is not reached, then reusing the two-dimensional function Halton sequence to initialize the population and the parameter, and continuing to executing subsequent steps until the iterative computation is ended in response to that the iteration termination condition is reached.
8 . A task scheduling device based on an improved chimpanzee optimization algorithm, comprising:
an initialization module, configured for obtaining a task to be scheduled and a task scheduling model pre-established by using the chimpanzee optimization algorithm, and initializing a population and a parameter by using a two-dimensional function Halton sequence; a computation module, configured for performing iterative computation of chimpanzees in the task scheduling model by the chimpanzee optimization algorithm; and an output module, configured for ending the iterative computation in response to that an iteration termination condition is reached, outputting an optimal solution, and obtaining an optimal scheduling scheme.
9 . A computer-readable storage medium, on which
a computer program is stored, wherein the computer program, when executed by a processor, implements the task scheduling method based on the improved chimpanzee optimization algorithm as claimed in claim 1 .
10 . An apparatus, comprising:
a memory for storing instructions; a processor for executing the instructions, wherein the device performs operations implementing the task scheduling method based on the improved chimpanzee optimization algorithm as claimed in claim 1 .Join the waitlist — get patent alerts
Track US2024411589A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.