2010-11-05 29 views
6

Vì vậy, tôi đang triển khai thuật toán heuristic và tôi đã thực hiện chức năng này.Hàm mật độ xác suất từ ​​giấy, được triển khai bằng C++, không hoạt động như dự định

Tôi có một mảng từ 1 đến n (0 đến n-1 trên C, w/e). Tôi muốn chọn một số yếu tố tôi sẽ sao chép sang mảng khác. Với tham số y, (0 < y < = 1), tôi muốn phân phối các số có giá trị trung bình là (y * n). Điều đó có nghĩa là bất cứ khi nào tôi gọi hàm này, nó cho tôi một số, giữa 0 và n, và trung bình của những con số này là y * n.

Theo tác giả, "l" là một số ngẫu nhiên: 0 < l < n. Trên mã thử nghiệm của nó, nó hiện đang tạo 0 < = l < = n. Và tôi đã có mã đúng, nhưng tôi đang lộn xộn với điều này trong nhiều giờ, và tôi lười để mã hóa nó lại.

Vì vậy, tôi đã mã hóa phần đầu tiên của hàm, cho y < = 0.5 Tôi đặt y thành 0,2 và n đến 100. Điều đó có nghĩa là phải trả lại số từ 0 đến 99, với mức trung bình 20. kết quả không nằm trong khoảng từ 0 đến n, nhưng một số kết quả nổi. Và n lớn hơn, nhỏ hơn phao này.

Đây là mã kiểm tra C. "x" là tham số "l".

//hate how code tag works, it's not even working now 
int n = 100; 
float y = 0.2; 
float n_copy; 

for(int i = 0 ; i < 20 ; i++) 
{ 
    float x = (float) (rand()/(float)RAND_MAX); // 0 <= x <= 1 
    x = x * n;        // 0 <= x <= n 
    float p1 = (1 - y)/(n*y); 
    float p2 = (1 - (x/n)); 
    float exp = (1 - (2*y))/y; 
    p2 = pow(p2, exp); 
    n_copy = p1 * p2; 
    printf("%.5f\n", n_copy); 
} 

Và đây là một số kết quả (5 thập phân cắt ngắn):

0.03354 
0.00484 
0.00003 
0.00029 
0.00020 
0.00028 
0.00263 
0.01619 
0.00032 
0.00000 
0.03598 
0.03975  
0.00704 
0.00176 
0.00001 
0.01333 
0.03396 
0.02795 
0.00005 
0.00860 

bài viết là:

http://www.scribd.com/doc/3097936/cAS-The-Cunning-Ant-System

trang 6 và 7.

hoặc tìm kiếm " cAS: hệ thống kiến ​​xảo quyệt "trên google.

Vì vậy, tôi đang làm gì sai? tôi không tin tác giả là sai, bởi vì có hơn 5 giấy tờ mô tả cùng chức năng này.

tất cả nội bộ của tôi cho bất kỳ ai giúp tôi. Điều này rất quan trọng đối với công việc của tôi.

Cảm ơn :)

+1

Không sử dụng thẻ mã. SO là khủng khiếp, nó sử dụng 4 dấu cách để chỉ ra mã. Chỉ cần sao chép mã, sau đó chọn tất cả và sau đó nhấn nút 1010 để làm cho mã. –

+3

Đó là vì hộp câu hỏi và câu trả lời sử dụng Markdown: http://daringfireball.net/projects/markdown/syntax – zwol

Trả lời

4

dmckee thực sự là chính xác, nhưng tôi nghĩ rằng tôi sẽ xây dựng nhiều hơn và cố gắng giải thích một số sự nhầm lẫn ở đây. Tôi chắc chắn có thể thất bại. f_s(l), hàm bạn có trong công thức đẹp ở trên, là hàm phân phối xác suất. Nó cho bạn biết, với một đầu vào cho trước l từ 0 đến n, xác suất l là độ dài phân đoạn. Tổng (tích phân) cho tất cả các giá trị từ 0 đến n phải bằng 1.

Biểu đồ ở đầu trang 7 làm lẫn lộn điểm này. Nó lô l so với f_s(l), nhưng bạn phải xem ra cho các yếu tố đi lạc nó đặt trên mặt. Bạn nhận thấy rằng các giá trị ở dưới cùng đi từ 0 đến 1, nhưng có một hệ số là x n ở bên cạnh, có nghĩa là giá trị l thực sự chuyển từ 0 sang n. Ngoài ra, trên trục y có x 1/n có nghĩa là các giá trị này không thực sự tăng lên khoảng 3, chúng chuyển thành 3/n.

Vì vậy, bạn sẽ làm gì bây giờ? Vâng, bạn cần phải giải quyết cho hàm phân phối tích lũy bằng cách tích hợp hàm phân phối xác suất trên l mà thực sự hóa ra không quá tệ (tôi đã làm nó với Tích hợp trực tuyến Mathrama Wolfram bằng cách sử dụng x cho l và chỉ sử dụng phương trình cho y < = .5). Tuy nhiên, đó là sử dụng một tích phân không xác định và bạn thực sự tích hợp dọc theo x từ 0 đến l. Nếu chúng ta đặt phương trình kết quả bằng một số biến (ví dụ z), mục tiêu bây giờ là giải quyết cho l như một hàm của z. z đây là một số ngẫu nhiên giữa 0 và 1. Bạn có thể thử sử dụng bộ giải mã tượng trưng cho phần này nếu bạn muốn (tôi muốn). Sau đó, bạn đã không chỉ đạt được mục tiêu của bạn là có thể chọn ngẫu nhiên l s từ phân phối này, bạn cũng đã đạt được niết bàn.

Một tác phẩm ít nhiều làm

tôi sẽ giúp hơn một chút. Tôi đã thử làm những gì tôi nói về y < = .5, nhưng hệ thống đại số tượng trưng mà tôi đã sử dụng không thể làm đảo ngược (một số hệ thống khác có thể). Tuy nhiên, sau đó tôi quyết định thử sử dụng phương trình cho .5 < y < = 1. Điều này hóa ra dễ dàng hơn nhiều.Nếu tôi thay đổi l để x trong f_s(l) tôi nhận được

y/n/(1 - y) * (x/n)^((2 * y - 1)/(1 - y)) 

Lồng ghép này qua x 0-l tôi (sử dụng trực tuyến tích hợp của Mathematica):

(l/n)^(y/(1 - y)) 

Nó không có được đẹp hơn nhiều so với với loại điều này. Nếu tôi đặt này tương đương với z và giải quyết cho l tôi nhận được:

l = n * z^(1/y - 1)  for .5 < y <= 1 

Một kiểm tra nhanh chóng là dành cho y = 1. Trong trường hợp này, chúng tôi nhận l = n dù là gì z. Càng xa càng tốt. Bây giờ, bạn chỉ cần tạo z (một số ngẫu nhiên giữa 0 và 1) và bạn nhận được một số l được phân phối theo ý muốn của bạn .5 < y < = 1. Nhưng hãy chờ xem đồ thị ở trang 7 bạn nhận thấy rằng xác suất chức năng phân phối là đối xứng. Điều đó có nghĩa là chúng tôi có thể sử dụng kết quả trên để tìm giá trị cho 0 < y < = .5. Chúng tôi chỉ cần thay đổi l ->n-ly ->1-y và nhận

n - l = n * z^(1/(1 - y) - 1) 

l = n * (1 - z^(1/(1 - y) - 1))  for 0 < y <= .5 

Dù sao, đó nên giải quyết vấn đề của bạn, trừ khi tôi thực hiện một số lỗi ở đâu đó. Chúc may mắn.

+0

Cảm ơn, Justin. Có viết câu trả lời của tôi về căn bản trực giác và tiêu đề bài viết tôi đã đi thực sự, bạn biết đấy, đọc bài báo - và tôi rất vui vì tôi đã làm đầy đủ mọi thứ tốt mà tôi chưa từng thấy trước đó. Trong mọi trường hợp, tôi nghĩ bạn đã đạt được một vài điểm quan trọng ở đây. Đáng chú ý là việc chuẩn hóa đã vượt quá [0, n], khi tôi ngây thơ mong đợi nó hơn [0,1). – dmckee

+0

@dmckee, vâng, tôi nghĩ công cụ này khá thú vị. Tôi đã đọc một chút về các loại thuật toán này, nhưng không nhiều. Tôi muốn tìm hiểu thêm về công cụ này. –

+0

Oh boy ... tôi thấy những yếu tố trên đồ thị, và tôi đã hiểu trục x, nhưng 'x 1/n' tôi đã bỏ qua. Vì vậy, tôi đọc văn bản của bạn, và tôi nhắc nhở hai năm của tôi về tính toán, nhưng tôi đã nói với bạn một cái gì đó .. đó là trong tiếng anh, và tôi không thể hiểu một điều (im Brazil, vì vậy khóa học của tôi là tiếng Bồ Đào Nha). Bạn có thể giúp tôi làm điều này một cách đơn giản nhất? tôi sẽ thực hiện điều này, và tôi muốn có hiệu suất tốt nhất, không quá nhiều tính toán để có được một số ngẫu nhiên phân phối bình thường. Btw, đây là nhiệm vụ cuối cùng của tôi về văn bằng của tôi, đó là về Hệ thống Ant và QAP. – hfingler

0

Cho rằng đối với bất kỳ giá trị l, y, n như mô tả, các từ ngữ bạn gọi p1 và p2 đều trong [0,1) và exp là trong [1, ..) làm pow (p2, exp) cũng trong [0,1) vì vậy tôi không thấy cách bạn có thể nhận được đầu ra với phạm vi [0, n)

6

Bạn có thể hiểu sai những gì được mong đợi của bạn.

Đưa ra một PDF (đúng chuẩn) và muốn phân phối ngẫu nhiên phù hợp với nó, bạn tạo Phân bổ xác suất tích lũy (CDF) bằng cách tích hợp PDF, rồi đảo ngược CDF và sử dụng một biến vị ngữ ngẫu nhiên đồng nhất đối số của hàm đảo ngược.


Chi tiết hơn một chút.

f_s(l) là PDF và đã được chuẩn hóa trên [0,n).

Bây giờ bạn có tích hợp nó để tạo thành CDF

g_s(l') = \int_0^{l'} dl f_s(l) 

Lưu ý rằng đây là một định thể thiếu đối với một thiết bị đầu cuối không xác định mà tôi đã gọi l'. CDF phù hợp với chức năng của l'. Giả sử chúng ta có quyền bình thường, g_s(N) = 1.0. Nếu đây không phải là chúng tôi áp dụng một hệ số đơn giản để sửa chữa nó.

Tiếp theo đảo ngược CDF và gọi kết quả G^{-1}(x). Đối với điều này, bạn có thể muốn chọn một giá trị cụ thể của gamma.

Sau đó, ném số ngẫu nhiên đồng nhất trên [0,n) và sử dụng số đó làm đối số, x, đến G^{-1}. Kết quả phải nằm giữa [0,1) và phải được phân phối theo f_s.

Giống như Justin đã nói, bạn có thể sử dụng hệ thống đại số máy tính cho môn toán.

+0

Vì vậy, 'f_s (l)' là một CDF? Tôi nên làm gì để lấy số ngẫu nhiên [0, n]? Xin lỗi, tôi không thực sự vào xác suất, tôi thực sự gần như đã bị từ chối (từ này âm thanh lạ .. dịch fro google) trên lớp xác suất. Dù sao, chúng tôi đã không học được những thứ như thế này .. Oh, cảm ơn lời giải thích của bạn :) – hfingler

+0

Vì vậy, cách duy nhất để có được số tôi muốn ([0, n] và với avg y), đang làm những gì bạn nói? Tôi không nghĩ rằng việc tích hợp sẽ là một ý tưởng hay, vì nó không đơn giản/nhanh chóng. Tôi cần điều này càng nhanh càng tốt, với ít tính toán hơn có thể. Nếu tôi phải làm điều đó, tôi nghĩ tôi sẽ nghiên cứu một số bản phân phối khác, đơn giản hơn. – hfingler

+0

@polar: Bạn muốn tích hợp và đảo ngược * biểu tượng * nếu có thể và chỉ thực hiện kết quả ('G^{- 1}') trong mã. Bạn ** chắc chắn ** không muốn tích hợp số trên mỗi lần vượt qua! Nếu bạn phải tích hợp số, bạn sẽ làm điều đó một lần và lưu trữ kết quả ngược lại dưới dạng biểu đồ chuẩn hóa. Có những câu hỏi khác về chi tiết đó làm thế nào để vẽ các con số với một biểu đồ. Bạn cũng có thể tìm thấy tất cả điều này trong hầu hết các văn bản phân tích số. – dmckee

Các vấn đề liên quan