結果

問題 No.453 製薬会社
ユーザー Yuki_UtaaiYuki_Utaai
提出日時 2018-05-05 00:48:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,059 ms / 2,000 ms
コード長 4,067 bytes
コンパイル時間 474 ms
コンパイル使用メモリ 87,084 KB
実行使用メモリ 87,344 KB
最終ジャッジ日時 2023-09-10 10:03:45
合計ジャッジ時間 15,059 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 959 ms
86,300 KB
testcase_01 AC 949 ms
85,988 KB
testcase_02 AC 980 ms
85,676 KB
testcase_03 AC 944 ms
86,648 KB
testcase_04 AC 931 ms
85,828 KB
testcase_05 AC 882 ms
83,828 KB
testcase_06 AC 1,030 ms
86,588 KB
testcase_07 AC 1,059 ms
86,924 KB
testcase_08 AC 935 ms
86,400 KB
testcase_09 AC 958 ms
86,004 KB
testcase_10 AC 998 ms
87,344 KB
testcase_11 AC 983 ms
86,880 KB
testcase_12 AC 960 ms
85,528 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random
import bisect

#大　域　探　索　型　人　工　蜂　コ　ロ　ニ　ー　ア　ル　ゴ　リ　ズ　ム

#評価関数:
def criterion(x, y):
    stock_c = w - 0.75 * x - 2/7 * y
    stock_d = h - 0.25 * x - 5/7 * y
    z = 1000 * x + 2000 * y
    if stock_c < 0 or stock_d < 0 or x < 0 or y < 0:
        z = 0.000001 #1/abs(z)
    return z

#働き蜂や見物蜂による探索
def employed_bee(x, y, xm, ym, c=1, alpha=1):
    v1, v2 = x, y
    r1= random.uniform(0, 1)
    r2= random.uniform(0, 1)
    phi1 = random.uniform(-c, c)
    phi2 = random.uniform(-c, c)
    if r1 <= alpha:
        v1 = x + phi1 * ( x - xm )
    if r2 <= alpha:
        v2 = y + phi2 * ( y - ym )
    return v1, v2

#ルーレット選択
def roulette_choice1(w):
    tot = []
    acc = 0
    for e in w:
        acc += e
        tot.append(acc)
    r = random.random() * acc
    for i, e in enumerate(tot):
        if r < e:
            return i

def main():
    N = 100  #個体数
    x_min, x_max = 0, 2*w
    y_min, y_max = 0, 2*h

    #個体座標, パーソナルベスト, グローバルベストの初期化を行う
    ps = [[random.uniform(x_min, 0.5*x_max), random.uniform(y_min, 0.5*y_max)] for i in range(N)]

    tc=[0 for i in range(N)]

    personal_best_scores = [criterion(p[0], p[1]) for p in ps]
    best_score = max(personal_best_scores)
    best_particle = personal_best_scores.index(max(personal_best_scores))
    global_best_position = ps[best_particle][:]


    T = 2400  #世代数(ループの回数)
    for t in range(T):

        #働き蜂による探索
        for n in range(N):
            m1 = random.randint(0, N-1)
            m2 = random.randint(0, N-1)
            
            new_x, new_y= employed_bee(ps[n][0], ps[n][1], ps[m1][0], ps[m2][1])

            f_x = personal_best_scores[n]
            f_v = criterion(new_x, new_y)

            stock_c = w - 0.75 * new_x - 2/7 * new_y
            stock_d = h - 0.25 * new_x - 5/7 * new_y

            if f_v > f_x and stock_c >= 0 and stock_d >= 0 and new_x >= 0 and new_y >= 0:
                ps[n][0] = new_x
                ps[n][1] = new_y
                personal_best_scores[n] = f_v
                tc[n] = 0

            else:
                tc[n] += 1

        #見物蜂による探索
        on_bee = roulette_choice1(personal_best_scores)
        if on_bee == None: print(ps, personal_best_scores)

        for n in range(N):
            
            m1 = random.randint(0, N-1)
            m2 = random.randint(0, N-1)

            new_x, new_y= employed_bee(ps[on_bee][0], ps[on_bee][1], ps[m1][0], ps[m2][1])
            f_x = personal_best_scores[on_bee]
            f_v = criterion(new_x, new_y)

            stock_c = w - 0.75 * new_x - 2/7 * new_y
            stock_d = h - 0.25 * new_x - 5/7 * new_y

            if f_v > f_x and stock_c >= 0 and stock_d >= 0 and new_x >= 0 and new_y >= 0:
                ps[on_bee][0] = new_x
                ps[on_bee][1] = new_y
                personal_best_scores[on_bee] = f_v
                tc[on_bee] = 0
            else:
                tc[on_bee] += 1

        #偵察蜂による探索
        for i in range(N):
            if tc[i] >= 100 * N:
                r1 = random.uniform(0, 1)
                r2 = random.uniform(0, 1)
                ps[i][0] = x_min + r1 * ( x_max - x_min )
                ps[i][1] = y_min + r2 * ( y_max - y_min )
                tc[i] = 0
                personal_best_scores[i] = criterion(ps[i][0], ps[i][1])

        #グローバルベストの更新を行う
        if max(personal_best_scores) > best_score:
            best_score = max(personal_best_scores)
            best_particle = personal_best_scores.index(max(personal_best_scores))
            global_best_position = ps[best_particle][:]

    #最適解
#    print(best_score, global_best_position)
    return best_score
#--------------------------------------------------------------

w, h=[int(i) for i in input().split()]
best=0
for i in range(2):
    best=max(best, main())
print(best)
0