查看: 2536|回复: 0

爬山算法

字体大小: 正常放大

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

发表于 2024-4-26 15:44 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

使用爬山算法优化简单的数学函数

假设我们需要找到函数 𝑓(𝑥)=−𝑥^2+4𝑥的最大值。这是一个具有单个局部最大值的简单抛物线函数。

步骤 1: 定义目标函数

首先，定义我们需要优化的函数。在MATLAB中，我们可以创建一个函数来计算给定x值的 𝑓(𝑥)。

function y = myFunction(x)- M1 J: @1 X) M6 V; I2 {) {/ v
y = -x^2 + 4*x;, \4 t- f: P# @7 Q) S
end

步骤 2: 实现爬山算法

接着，实现爬山算法。我们从一个随机点开始，然后在每一步尝试移动到一个“邻居”点，如果那里的值更高，就移动到那里。

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)5 R+ J7 s+ [/ c% f0 h
currentX = initialX;; r: p# |3 M( \9 K7 u' c: ]$ a, ?! U
currentY = func(currentX);
6 _6 X ~7 B# E! g
for i = 1:numIterations, r, Q: |3 g, ~! }. t/ F3 J
% 尝试在两个方向上移动% Z# G2 [3 D1 N
newX = [currentX + stepSize, currentX - stepSize];5 l2 @3 Q. }' T3 z+ c# x( A
newY = [func(newX(1)), func(newX(2))];' f' n2 U& D& {* n+ O1 u$ u
4 z, U0 N# h. O3 n, `6 S
% 找出最好的移动方向
3 U' x. e\\" f5 Z) j
[maxY, idx] = max(newY);
2 B$ r# e' M8 q0 _# ]
! c6 x1 X4 V- p1 ]' \) L, S6 `' ~
% 如果找到了更好的解，则更新当前解
: C c3 ~- H& q4 \- g. X L
if maxY > currentY
# T& X% ?* i( |4 X
currentX = newX(idx);4 S6 I+ M, o7 z
currentY = maxY;
+ k/ f\\" J0 Y' [9 E9 n; a3 C
else: ~( i2 ?( p; X( Y: b8 x
% 如果没有更好的解，结束搜索2 z' Z\\" f$ d; [, _
break;$ \' ]5 K7 i) m: p# n# s: E
end
' O b7 l7 [, M M: j6 Z: U; V
end
) O }- I. ?( J0 a6 h/ U) @/ n; {
bestX = currentX;9 u9 _/ K; Z# O; i
bestY = currentY;4 g9 A' z: Q$ z7 q6 o! D& `6 \
end
% o' F\\" H\\" `( v+ k% L
* k. B\\" y6 N- E* o\\" z1 B$ R& f
% 运行爬山算法
5 a0 c+ |9 e3 t/ f) a& x4 z
initialX = 0; % 初始点! }% b: d6 r0 I% U1 b2 j6 ?
stepSize = 0.1; % 步长6 v6 N6 p/ I% _% ]4 f# J4 N# C\\" M. c
numIterations = 100; % 迭代次数
; ]0 h! {2 M, @& N* E0 \0 Y
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)5 R+ J7 s+ [/ c% f0 h

currentX = initialX;; r: p# |3 M( \9 K7 u' c: ]$ a, ?! U

currentY = func(currentX); 
6 _6 X  ~7 B# E! g
    for i = 1:numIterations, r, Q: |3 g, ~! }. t/ F3 J

% 尝试在两个方向上移动% Z# G2 [3 D1 N

newX = [currentX + stepSize, currentX - stepSize];5 l2 @3 Q. }' T3 z+ c# x( A

newY = [func(newX(1)), func(newX(2))];' f' n2 U& D& {* n+ O1 u$ u

4 z, U0 N# h. O3 n, `6 S
        % 找出最好的移动方向 
3 U' x. e\\" f5 Z) j
        [maxY, idx] = max(newY); 
2 B$ r# e' M8 q0 _# ]
         
! c6 x1 X4 V- p1 ]' \) L, S6 `' ~
        % 如果找到了更好的解，则更新当前解 
: C  c3 ~- H& q4 \- g. X  L
        if maxY > currentY 
# T& X% ?* i( |4 X
            currentX = newX(idx);4 S6 I+ M, o7 z

currentY = maxY; 
+ k/ f\\" J0 Y' [9 E9 n; a3 C
        else: ~( i2 ?( p; X( Y: b8 x

% 如果没有更好的解，结束搜索2 z' Z\\" f$ d; [, _

break;$ \' ]5 K7 i) m: p# n# s: E

end 
' O  b7 l7 [, M  M: j6 Z: U; V
    end 
) O  }- I. ?( J0 a6 h/ U) @/ n; {
    bestX = currentX;9 u9 _/ K; Z# O; i

bestY = currentY;4 g9 A' z: Q$ z7 q6 o! D& `6 \

end 
% o' F\\" H\\" `( v+ k% L
 * k. B\\" y6 N- E* o\\" z1 B$ R& f

% 运行爬山算法 
5 a0 c+ |9 e3 t/ f) a& x4 z
initialX = 0; % 初始点! }% b: d6 r0 I% U1 b2 j6 ?

stepSize = 0.1; % 步长6 v6 N6 p/ I% _% ]4 f# J4 N# C\\" M. c

numIterations = 100; % 迭代次数 
; ]0 h! {2 M, @& N* E0 \0 Y
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

步骤 3: 输出结果

展示算法找到的最优解。

disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);
' a! D. Z4 e\" \: V# Q! ^6 b
disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

可视化函数和算法找到的最大值点，以更好地理解算法的行为。